﻿/*
 * 注意: 
 * 高精度会更平滑, 低精度有锯齿, 如下:
 * ab连线与 m-m1,n-n1的交点均不在精度格上, 如果将交点四舍五入到精度格上再判断交点是否在ab上则肯定失败
 * a-------m1------n1------*
 * |       |       |       |
 * |       |       |       |
 * |       |       |       |
 * o-------m-------n-------b
 */

using Clipper2Lib;

namespace SmallGeo;

public static class Util
{
    public const double DEG2RAD = Math.PI / 180;
    public const double RAD2DEG = 180 / Math.PI;

    #region 向量内积和外积
    /// <summary>
    /// 内积, 又称数量积/点积/点乘<br/>
    /// （x1,y1) dot (x2,y2) = x1*x2 + y1*y2
    /// </summary>
    public static double Dot(Vector2d value1, Vector2d value2)
    {
        return value1.X * value2.X + value1.Y * value2.Y;
    }
    /// <summary>
    /// 内积, 又称数量积/点积/点乘<br/>
    /// （x1,y1,z1) dot (x2,y2,z2) = x1*x2 + y1*y2 + z1*z2
    /// </summary>
    public static double Dot(Vector3d value1, Vector3d value2)
    {
        return value1.X * value2.X + value1.Y * value2.Y + value1.Z * value2.Z;
    }
    /// <summary>
    /// 叉积, 又称向量积/外积/叉乘, 向量a cross 向量b = |a||b|sinθ<br/>
    /// 表示: 向量a和向量b平行四边形的面积, 当平行时返回0
    /// </summary>
    public static double Cross(Vector2d value1, Vector2d value2)
    {
        return value1.X * value2.Y - value2.X * value1.Y;
    }
    /// <summary>
    /// 叉积, 又称向量积, 便捷写法, 相当于 Cross(a - origin, b - origin)<br/>
    /// 参考: <seealso cref="Cross(Vector2d, Vector2d)"/>
    /// </summary>
    public static double Cross(Vector2d a, Vector2d origin, Vector2d b)
        => Cross(a - origin, b - origin);
    /// <summary>
    /// 叉积, 又称向量积, 结果是一个法向量, 遵循右手法则, 比如: <br/>
    /// (1,0,0) cross (0,1,0) => (0,0,1), 而不是 (0,0,-1)
    /// </summary>
    public static Vector3d Cross(Vector3d value1, Vector3d value2)
    {
        return new Vector3d
        {
            X = value1.Y * value2.Z - value1.Z * value2.Y,
            Y = value1.Z * value2.X - value1.X * value2.Z,
            Z = value1.X * value2.Y - value1.Y * value2.X
        };
    }

    /// <summary>
    /// 叉积, 又称向量积, 便捷写法, 相当于 Cross(a - origin, b - origin)<br/>
    /// 参考: <seealso cref="Cross(Vector3d, Vector3d)"/>
    /// </summary>
    public static Vector3d Cross(Vector3d a, Vector3d origin, Vector3d b)
        => Cross(a - origin, b - origin);
    #endregion

    #region 四舍五入
    public static Vector2d Round(Vector2d vector, int digits = 4) =>
        new(Math.Round(vector.X, digits), Math.Round(vector.Y, digits));
    public static Vector3d Round(Vector3d vector, int digits = 4) =>
        new(Math.Round(vector.X, digits), Math.Round(vector.Y, digits), Math.Round(vector.Z, digits));
    #endregion

    #region 规范转换角度
    /// <summary>
    /// 将弧度制转为区间: [0,Pi/2] , 就像两条直线的夹角一样
    /// </summary>
    /// <param name="radian"></param>
    /// <returns></returns>
    public static double NormalRadianLikeLine(double radian)
    {
        //先转到[0,180)之间
        while (radian < 0) radian += Math.PI;
        while (radian >= Math.PI) radian -= Math.PI;
        return radian > Math.PI / 2 ? (Math.PI - radian) : radian;
    }

    /// <summary>
    /// 将弧度制转为区间: (-Pi,Pi] , 就像两条向量的夹角一样
    /// </summary>
    /// <param name="radian"></param>
    /// <returns></returns>
    public static double NormalRadianLikeVector(double radian)
    {
        //转到(-180,180]之间
        while (radian <= -Math.PI) radian += Math.PI * 2;
        while (radian > Math.PI) radian -= Math.PI * 2;
        return radian;
    }

    /// <summary>
    /// 将弧度制转为区间: [0,Pi] , 就像两条向量的夹角一样(忽略顺逆时针)
    /// </summary>
    /// <param name="radian"></param>
    /// <returns></returns>
    public static double NormalRadianLikeVectorIgnoreClock(double radian)
    {
        //先转到[-180,180]之间
        while (radian < -Math.PI) radian += Math.PI * 2;
        while (radian > Math.PI) radian -= Math.PI * 2;
        return Math.Abs(radian);
    }
    #endregion

    #region 弧度制角度制互转
    /// <summary>
    /// 角度转弧度,如: 180° => 3.141592653589793
    /// </summary>
    public static double ToRadian(double degree) => degree * DEG2RAD;

    /// <summary>
    /// 弧度转角度,如: 3.141592653589793 => 180°
    /// </summary>
    public static double ToDegree(double radian) => radian * RAD2DEG;
    #endregion

    #region 长度
    /// <summary>
    /// 长度
    /// </summary>
    public static double Length(Vector2d v)
        => Math.Sqrt(LengthSquared(v));

    /// <summary>
    /// 长度的平方
    /// </summary>
    public static double LengthSquared(Vector2d v)
        => Dot(v, v);

    /// <summary>
    /// 长度
    /// </summary>
    public static double Length(Vector3d v)
        => Math.Sqrt(LengthSquared(v));

    /// <summary>
    /// 长度的平方
    /// </summary>
    public static double LengthSquared(Vector3d v)
        => Dot(v, v);

    /// <summary>
    /// 线段长度
    /// </summary>
    public static double Length(LineSegment2d line)
        => Length(line.P0 - line.P1);

    /// <summary>
    /// 线段长度
    /// </summary>
    public static double Length(LineSegment3d line)
        => Length(line.P0 - line.P1);
    #endregion

    #region 向量和点和线段互转
    public static Vector2d ToXY(LineSegment2d line)
    {
        if (line == null) throw new Exception($"无法将 null 转为 XY, LineSegment2d 不能为空!");
        return new Vector2d
        {
            X = line.P1.X - line.P0.X,
            Y = line.P1.Y - line.P0.Y,
        };
    }
    public static Vector3d ToXYZ(LineSegment3d line)
    {
        if (line == null) throw new Exception($"无法将 null 转为 XYZ, LineSegment3d 不能为空!");
        return new Vector3d
        {
            X = line.P1.X - line.P0.X,
            Y = line.P1.Y - line.P0.Y,
            Z = line.P1.Z - line.P0.Z,
        };
    }
    public static LineSegment2d ToLineSegment(Vector2d point)
    {
        return new LineSegment2d
        {
            P0 = Vector2d.Zero,
            P1 = point
        };
    }
    public static LineSegment3d ToLineSegment(Vector3d point)
    {
        return new LineSegment3d
        {
            P0 = Vector3d.Zero,
            P1 = point
        };
    }
    #endregion

    #region 向量长度归一化
    /// <summary>
    /// 长度归一化
    /// </summary>
    public static Vector2d Normalized(Vector2d vector2d)
    {
        var len = Length(vector2d);
        if (len == 0) return vector2d;
        return new Vector2d()
        {
            X = vector2d.X / len,
            Y = vector2d.Y / len,
        };
    }

    /// <summary>
    /// 长度归一化
    /// </summary>
    public static Vector3d Normalized(Vector3d vector3d)
    {
        var len = Length(vector3d);
        if (len == 0) return vector3d;
        return new Vector3d()
        {
            X = vector3d.X / len,
            Y = vector3d.Y / len,
            Z = vector3d.Z / len,
        };
    }
    #endregion

    #region 求直线或向量的垂线
    /// <summary>
    /// 求向量的垂线
    /// </summary>
    public static Vector2d GetVectorPerpendicular(Vector2d vector, bool isCounterClock = true)
    {
        if (vector == Vector2d.Zero) return Vector2d.Zero;
        if (isCounterClock) return new Vector2d(-vector.Y, vector.X);
        return new Vector2d(vector.Y, -vector.X);
    }
    /// <summary>
    /// 求线段的垂线, 默认以 P0 为原点, 顺逆时针旋转90°
    /// <code>
    /// 逆时针旋转:
    /// P1(new)
    /// |
    /// |
    /// |
    /// P0------P1(old)
    /// 
    /// 顺时针旋转:
    /// P0------P1(old)
    /// |
    /// |
    /// |
    /// P1(new)
    /// </code>
    /// 也可以指定旋转的原点, 参数: origin
    /// <list type="bullet">
    /// <item>0或其他: P0</item>
    /// <item>1: P1</item>
    /// <item>2: 中点</item>
    /// </list>
    /// </summary>
    public static LineSegment2d GetLinePerpendicular(LineSegment2d line, bool isCounterClockWise = true, int origin = 0)
    {
        if (line == null || line.Length() == 0) throw new Exception($"无法对不合法的线求其垂线!");
        var v = line.ToVector();
        var dir = GetVectorPerpendicular(v, isCounterClockWise);
        if (origin == 2)
            return new LineSegment2d((line.P0 + line.P1) / 2 - dir / 2, (line.P0 + line.P1) / 2 + dir / 2);
        else if (origin == 1)
            return new LineSegment2d(line.P1 - dir, line.P1);
        return new LineSegment2d(line.P0, line.P0 + dir);
    }
    #endregion

    #region 两个点或向量是否近似相等
    /// <summary>
    /// 两个点或向量是否近似相等, 距离在 tolerance 范围内则认为是相等
    /// </summary>
    public static bool IsNearlySame(Vector2d point, Vector2d pointOther, double tolerance = 0.0001)
        => Length(point - pointOther) <= tolerance;
    /// <summary>
    /// 两个点或向量是否近似相等, 距离在 tolerance 范围内则认为是相等
    /// </summary>
    public static bool IsNearlySame(Vector3d point, Vector3d pointOther, double tolerance = 0.0001)
        => Length(point - pointOther) <= tolerance;
    #endregion

    #region 计算向量或线段间夹角
    /// <summary>
    /// 计算向量与x轴正方向的夹角,弧度制,逆时针为正,值域: (-PI, PI]
    /// <code>
    /// Math.Atan2(0, 0); //0
    /// Math.Atan2(0, 1); //0
    /// Math.Atan2(0, -1); //Math.PI
    /// Math.Atan2(1, 0); //Math.PI/2
    /// Math.Atan2(-1, 0); //-Math.PI/2
    /// </code>
    /// </summary>
    public static double AngleRadian(Vector2d vector)
        //Atan2已经处理了极值情况
        => Math.Atan2(vector.Y, vector.X);

    /// <summary>
    /// 计算向量与x轴正方向的夹角,角度制,逆时针为正,值域: (-180, 180]
    /// <code>
    /// Math.Atan2(0, 0); //0
    /// Math.Atan2(0, 1); //0
    /// Math.Atan2(0, -1); //180
    /// Math.Atan2(1, 0); //90
    /// Math.Atan2(-1, 0); //-90
    /// </code>
    /// </summary>
    public static double AngleDegree(Vector2d vector)
        => AngleRadian(vector).ToDegree();

    /// <summary>
    /// 计算向量与x轴正方向的夹角,弧度制,忽略顺逆时针,值域: [0, PI]
    /// </summary>
    public static double AngleRadianIgnoreClock(Vector2d vector)
        => Math.Abs(AngleRadian(vector));

    /// <summary>
    /// 计算向量间的夹角,弧度制,逆时针为正,值域: (-PI, PI]
    /// </summary>
    public static double AngleRadian(Vector2d vectorStart, Vector2d vectorEnd)
    {
        var radian1 = AngleRadian(vectorStart);
        var radian2 = AngleRadian(vectorEnd);
        return NormalRadianLikeVector(radian2 - radian1);
    }

    /// <summary>
    /// 计算向量间的夹角,角度制,逆时针为正,值域: (-180, 180]
    /// </summary>
    public static double AngleDegree(Vector2d vectorStart, Vector2d vectorEnd)
        => AngleRadian(vectorStart, vectorEnd).ToDegree();

    /// <summary>
    /// 计算向量间的夹角,弧度制,忽略顺逆时针,值域: [0, PI]
    /// </summary>
    public static double AngleRadianIgnoreClock(Vector2d vectorStart, Vector2d vectorEnd)
    {
        var radian1 = AngleRadian(vectorStart);
        var radian2 = AngleRadian(vectorEnd);
        return NormalRadianLikeVectorIgnoreClock(radian1 - radian2);
    }

    /// <summary>
    /// 计算向量间的夹角,角度制,忽略顺逆时针,值域: [0, 180]
    /// </summary>
    public static double AngleDegreeIgnoreClock(Vector2d vectorStart, Vector2d vectorEnd)
        => AngleRadianIgnoreClock(vectorStart, vectorEnd).ToDegree();

    /// <summary>
    /// 计算两线段表示的直线间的夹角, 值域: [0,PI/2]
    /// </summary>
    public static double AngleRadian(LineSegment2d line, LineSegment2d line2)
    {
        if (line == null || line2 == null) throw new Exception($"无法计算 LineSegment2d 为 null 的夹角!");
        return (line.P1 - line.P0).AngleRadian((line2.P1 - line2.P0)).NormalRadianLikeLine();
    }

    /// <summary>
    /// 计算两线段表示的直线间的夹角, 值域: [0,90]
    /// </summary>
    public static double AngleDegree(LineSegment2d line, LineSegment2d line2)
        => AngleRadian(line, line2).ToDegree();

    /// <summary>
    /// 计算两条平行线间的距离, 原理如下:
    /// <code>
    /// line 的中心点向 line2 投影, 计算投影点(proj) 和 center 之间的距离
    /// 
    ///  line x--------center-------------x
    ///                  |
    ///                  |
    ///  line2          proj * * x---------x
    /// </code>
    /// </summary>
    public static double DistanceBetweenParallelLineSegments(LineSegment2d line, LineSegment2d line2)
    {
        var proj = Util.ProjectOnLine(line.Center(), line2.P0, line2.P1);
        return proj.DistanceTo(line.Center());
    }

    //todo 3维向量间的夹角
    #endregion

    #region 判断两个向量是否近似同向、反向、垂直
    /// <summary>
    /// 两个向量的方向是否近似相同
    /// </summary>
    public static bool IsNearlySameDirection(Vector2d vector, Vector2d vectorOther, double degreeTolerance = 1)
    {
        var degree = AngleDegreeIgnoreClock(vector, vectorOther);
        return degree <= degreeTolerance;
    }

    /// <summary>
    /// 两个向量的方向是否近似相反
    /// </summary>
    public static bool IsNearlyOppositeDirection(Vector2d vector, Vector2d vectorOther, double degreeTolerance = 1)
    {
        var degree = AngleDegreeIgnoreClock(vector, vectorOther);
        return (180 - degree) <= degreeTolerance;
    }

    /// <summary>
    /// 两个向量的方向是否近似相同或相反
    /// </summary>
    public static bool IsNearlySameOrOppositeDirection(Vector2d vector, Vector2d vectorOther, double degreeTolerance = 1)
    {
        var degree = AngleDegreeIgnoreClock(vector, vectorOther);
        return (degree > 90 ? (180 - degree) : degree) <= degreeTolerance;
    }

    /// <summary>
    /// 两个向量是否近似垂直
    /// </summary>
    public static bool IsNearlyPerpendicular(Vector2d vector, Vector2d vectorOther, double degreeTolerance = 1)
    {
        var degree = AngleDegreeIgnoreClock(vector, vectorOther);
        return Math.Abs(90 - degree) <= degreeTolerance;
    }

    /// <summary>
    /// 两个向量是否近似平行, 同: <seealso cref="IsNearlySameOrOppositeDirection(Vector2d, Vector2d, double)"/>
    /// </summary>
    public static bool IsNearlyParaller(Vector2d vector, Vector2d vectorOther, double degreeTolerance = 1)
        => IsNearlySameOrOppositeDirection(vector, vectorOther, degreeTolerance);
    #endregion

    #region 点或向量的平移、旋转、缩放

    #region 2d
    /// <summary>
    /// 将点绕原点旋转指定度数(弧度制),逆时针为正
    /// </summary>
    public static Vector2d RotateRadian(Vector2d point, double radian)
    {
        var m = Matrix_3x3.FromRotation(radian);
        return new Vector2d
        {
            X = m.a11 * point.X + m.a12 * point.Y + m.a13,
            Y = m.a21 * point.X + m.a22 * point.Y + m.a23,
        };
    }
    /// <summary>
    /// 将点绕原点旋转指定度数(角度制),逆时针为正
    /// </summary>
    public static Vector2d RotateDegree(Vector2d point, double degree)
    {
        var degreeMod = ((degree % 360) + 360) % 360;
        return degreeMod switch
        {
            0 => point,
            90 => new Vector2d(-point.Y, point.X),
            180 => new Vector2d(-point.X, -point.Y),
            270 => new Vector2d(point.Y, -point.X),
            _ => RotateRadian(point, degree.ToRadian()),
        };
    }
    /// <summary>
    /// 将点绕指定点旋转指定度数(弧度制),逆时针为正
    /// </summary>
    public static Vector2d RotateRadian(Vector2d point, Vector2d origin, double radian)
        => Matrix_3x3.FromRotation(origin, radian).Apply(point);
    /// <summary>
    /// 将点绕指定点旋转指定度数(角度制),逆时针为正
    /// </summary>
    public static Vector2d RotateDegree(Vector2d point, Vector2d origin, double degree)
    {
        if (origin == Vector2d.Zero) return RotateDegree(point, degree);
        return RotateRadian(point, origin, degree.ToRadian());
    }
    /// <summary>
    /// 将点平移指定的距离
    /// </summary>
    public static Vector2d Translate(Vector2d point, double x, double y)
        => Matrix_3x3.FromTranslate(x, y).Apply(point);
    /// <summary>
    /// 将点缩放指定的倍数
    /// </summary>
    public static Vector2d Scale(Vector2d point, double x, double y)
        => Matrix_3x3.FromScale(x, y).Apply(point);
    /// <summary>
    /// 将点缩放指定的倍数,相对指定位置
    /// </summary>
    public static Vector2d Scale(Vector2d point, Vector2d origin, double x, double y)
        => Matrix_3x3.FromScale(origin, x, y).Apply(point);

    /// <summary>
    /// 将线绕指定点逆时针旋转指定度数, 默认绕 line.P0 旋转
    /// </summary>
    /// <remarks> 注意: 更改了自身</remarks>
    public static LineSegment2d Rotate(LineSegment2d line, double radian, Vector2d? origin = null)
    {
        if (line == null) return null;
        if (origin == null) origin = line.P0;
        var newP0 = Util.RotateRadian(line.P0, origin.Value, radian);
        var newP1 = Util.RotateRadian(line.P1, origin.Value, radian);
        line.P0 = newP0;
        line.P1 = newP1;
        return line;
    }
    #endregion

    #region 3d
    /// <summary>
    /// 将点绕x轴旋转指定度数
    /// </summary>
    public static Vector3d RotateX(Vector3d point, double radian)
        => Matrix_4x4.FromRotationX(radian).Apply(point);
    /// <summary>
    /// 将点绕经过 throughPoint 的x方向轴旋转指定度数
    /// </summary>
    public static Vector3d RotateX(Vector3d point, Vector3d throughPoint, double radian)
        => Matrix_4x4.FromRotationX(throughPoint, radian).Apply(point);
    /// <summary>
    /// 将点绕y轴旋转指定度数
    /// </summary>
    public static Vector3d RotateY(Vector3d point, double radian)
        => Matrix_4x4.FromRotationY(radian).Apply(point);
    /// <summary>
    /// 将点绕经过 throughPoint 的y方向轴旋转指定度数
    /// </summary>
    public static Vector3d RotateY(Vector3d point, Vector3d throughPoint, double radian)
        => Matrix_4x4.FromRotationY(throughPoint, radian).Apply(point);
    /// <summary>
    /// 将点绕z轴旋转指定度数
    /// </summary>
    public static Vector3d RotateZ(Vector3d point, double radian)
        => Matrix_4x4.FromRotationZ(radian).Apply(point);
    /// <summary>
    /// 将点绕经过 throughPoint 的z方向轴旋转指定度数
    /// </summary>
    public static Vector3d RotateZ(Vector3d point, Vector3d throughPoint, double radian)
        => Matrix_4x4.FromRotationZ(throughPoint, radian).Apply(point);

    /// <summary>
    /// 将点绕过原点的指定方向轴旋转
    /// </summary>
    public static Vector3d RotateAxis(Vector3d point, Vector3d axis, double radian)
        => Matrix_4x4.FromRotationAxis(axis, radian).Apply(point);
    /// <summary>
    /// 将点绕过 throughPoint 的指定方向轴旋转
    /// </summary>
    public static Vector3d RotateAxis(Vector3d point, Vector3d throughPoint, Vector3d axis, double radian)
        => Matrix_4x4.FromRotationAxis(throughPoint, axis, radian).Apply(point);

    public static Vector3d Translate(Vector3d point, double x, double y, double z)
        => Matrix_4x4.FromTranslate(x, y, z).Apply(point);
    public static Vector3d Scale(Vector3d point, double x, double y, double z)
        => Matrix_4x4.FromScale(x, y, z).Apply(point);
    public static Vector3d Scale(Vector3d point, Vector3d origin, double x, double y, double z)
        => Matrix_4x4.FromScale(origin, x, y, z).Apply(point);
    #endregion

    //todo: 3d中旋转方向 右手坐标系 逆时针为正??

    #endregion

    #region 是否是简单多边形 IsNearySimplePolygon
    /// <summary>
    /// 判断多边形是否是简单的(边不能近似相交,距离容差为 tolerance)
    /// </summary>
    /// <param name="points">点位(兼容首尾相同或不相同情况)</param>
    /// <param name="tolerance">判断点位近似相等的容差,两点位距离小于等于此值,则认为点位相等,自然polygon就不是Simple了</param>
    /// <returns></returns>
    public static bool IsNearySimplePolygon(List<Vector2d> points, double tolerance = 0.0001)
    {
        if (points == null || points.Count() < 3) return false;

        var len = points.Count();
        if (points[0] == points.Last())
        {
            len -= 1;
            if (len < 3) return false;
        }
        if (len == 3)
        {
            //三角形
            //3个点都不能近似相等
            if (points[0].IsNearlySame(points[1], tolerance) || points[0].IsNearlySame(points[2], tolerance) || points[1].IsNearlySame(points[2], tolerance)) return false;
            //防止在一条直线上
            return IsNearlyPointOnLineSegment(points[0], new LineSegment2d(points[1], points[2]), tolerance);
        }

        //判断边是否相交
        // 对于下面的图形, 依次遍历, 如:
        //  AB不能与CD/DE/EF相交
        //  BC不能与DE/EF/FA相交
        // A-----B
        // |     |
        // |     C-----D
        // |           |
        // |           |
        // F-----------E
        //
        for (var i = 1; i < len; i++)
        {
            var line = new LineSegment2d
            {
                P0 = points[i],
                P1 = points[(i + 1) % len]
            };
            var idx = (i + 2) % len;
            while ((idx + 1) % len != i)
            {
                var line2 = new LineSegment2d
                {
                    P0 = points[idx],
                    P1 = points[(idx + 1) % len],
                };
                if (line.IsNearyIntersect(line2, tolerance)) return false;
                idx = (idx + 1) % len;
            }
        }
        return true;
    }
    #endregion

    #region 针对一个多边形计算一个合适的 uv轴 GetUV
    /// <summary>
    /// 计算多边形的uv轴(u长,v短, v是u逆时针转90°)
    /// <code>
    /// v
    /// |
    /// o-----u
    /// 
    ///        x--------x
    ///       /         |
    /// x----x          x
    /// |                \
    /// x-----------------x
    /// </code>
    /// </summary>
    /// <remarks>
    /// 注意: 不是最小的外接矩形, 这是选一个长边作为U轴
    /// </remarks>
    public static (Vector2d u, Vector2d v) GetUV(List<Vector2d> polygon, double degreeTolerance = 1)
    {
        var lens = polygon.Select((i, idx) =>
        {
            var cur = i;
            var next = polygon[(idx + 1) % polygon.Count];
            return (next - cur).Length();
        }).ToList();
        var maxLen = lens.Max();
        var maxLenIdx = lens.IndexOf(maxLen);
        //确定 u v 轴, 认为u轴长
        var u = (polygon[(maxLenIdx + 1) % polygon.Count] - polygon[maxLenIdx]).Normalized();
        var degree = u.AngleRadian().NormalRadianLikeVectorIgnoreClock().ToDegree();
        if (degree < degreeTolerance || (180 - degree) < degreeTolerance) u = new Vector2d(1, 0);
        //逆时针转90°
        var v = new Vector2d(-u.Y, u.X);
        return (u, v);
    }
    #endregion

    #region 判断3点是否共线 IsNearlySameLine
    /// <summary>
    /// 判断3点(A/B/C)是否近似共线, 原理是: AC+BC ≈ AB<br/>
    /// 即: 点C分别到A和B的距离之和在误差范围内等于AB距离
    /// <code>
    ///     C
    /// A-------B
    /// </code>
    /// </summary>
    public static bool IsNearlySameLine(Vector3d point1, Vector3d point2, Vector3d point3, double tolerance = 0.0001)
    {
        var lens = new List<double>
        {
            (point1 - point2).Length(),
            (point1 - point3).Length(),
            (point2 - point3).Length()
        };
        lens = lens.OrderBy(i => i).ToList();
        return Math.Abs(lens[2] - (lens[0] + lens[1])) <= tolerance;
    }
    /// <summary>
    /// 判断3点(A/B/C)是否近似共线, 原理是: AC+BC ≈ AB<br/>
    /// 即: 点C分别到A和B的距离之和在误差范围内等于AB距离
    /// <code>
    ///     C
    /// A-------B
    /// </code>
    /// </summary>
    public static bool IsNearlySameLine(Vector2d point1, Vector2d point2, Vector2d point3, double tolerance = 0.0001)
    {
        var lens = new List<double>
        {
            (point1 - point2).Length(),
            (point1 - point3).Length(),
            (point2 - point3).Length()
        };
        lens = lens.OrderBy(i => i).ToList();
        return Math.Abs(lens[2] - (lens[0] + lens[1])) <= tolerance;
    }
    #endregion

    #region 计算面积
    /// <summary>
    /// 逆时针为正，顺时针为负
    /// </summary>
    public static double GetSignedArea(List<Vector2d> points)
    {
        if (points == null || points.Count == 0) throw new Exception($"必须是一个合法的polygon才能计算面积!");
        var len = points.Count;
        if (points.Last() == points.First())
        {
            len -= 1;
            if (len < 3) throw new Exception($"必须是一个合法的polygon才能计算面积!");
        }
        double sum = 0;

        for (int index = 0; index < len; ++index)
        {
            sum += Cross(points[index], points[(index + 1) % len]) / 2;
        }
        return sum;
    }

    /// <summary>
    /// 简单多边形的面积,忽略顺逆时针, 就是: Math.Abs(GetSignedArea(points))
    /// </summary>
    public static double GetArea(List<Vector2d> points)
        => Math.Abs(GetSignedArea(points));
    #endregion

    #region 计算三维面的法线 GetPolygonNormal
    /// <summary>
    /// 获取多边形的法线方向, 右手法则
    /// <code>
    ///         ↑
    ///     0---∣-----3
    ///    /    ∣    /
    ///   /         /
    ///  1---------2
    /// </code>
    /// </summary>
    public static Vector3d GetPolygonNormal(List<Vector3d> points)
    {
        if (points == null || points.Count == 0) return Vector3d.Zero;
        var len = points.Count;
        if (points.LastOrDefault() == points[0]) len--;
        if (len < 3) return Vector3d.Zero;
        var normals = new List<Vector3d>();
        for (int i = 0; i < points.Count; i++)
        {
            var currentPoint = points[i];
            var nextPoint = points[(i + 1) % points.Count];
            var nnPoint = points[(i + 2) % points.Count];
            normals.Add(Cross(nextPoint - currentPoint, nnPoint - nextPoint));
        }
        var v = new Vector3d(normals.Average(i => i.X), normals.Average(i => i.Y), normals.Average(i => i.Z));

        return v.Normalized();
    }
    #endregion

    #region 顺逆时针
    /// <summary>
    /// 是否是逆时针,一般: 逆时针表示面, 顺时针表示洞
    /// </summary>
    /// <param name="points"></param>
    /// <returns></returns>
    public static bool IsCounterClockWise(List<Vector2d> points)
        => GetSignedArea(points) > 0;

    /// <summary>
    /// 如果不是逆时针, 改成逆时针, 示例:
    /// <code>
    /// 原点位是顺时针:
    /// 0----------1
    /// |          |
    /// |          |
    /// 3----------2
    /// 
    /// 改为逆时针后:
    /// 3----------2
    /// |          |
    /// |          |
    /// 0----------1
    /// </code>
    /// </summary>
    /// <param name="points"></param>
    /// <returns></returns>
    public static List<Vector2d> ToCounterClockWise(List<Vector2d> points)
    {
        if (IsCounterClockWise(points)) return points;
        points.Reverse();
        return points;
    }

    /// <summary>
    /// 如果不是顺时针, 改成顺时针, 示例:
    /// <code>
    /// 原点位是逆时针:
    /// 3----------2
    /// |          |
    /// |          |
    /// 0----------1        
    /// 
    /// 改为顺时针后:
    /// 0----------1
    /// |          |
    /// |          |
    /// 3----------2
    /// </code>
    /// </summary>
    /// <param name="points"></param>
    /// <returns></returns>
    public static List<Vector2d> ToClockWise(List<Vector2d> points)
    {
        if (!IsCounterClockWise(points)) return points;
        points.Reverse();
        return points;
    }
    /// <summary>
    /// 判断从 startDir 旋转到 endDir 是否是逆时针旋转<br/>
    /// 这里的难点在于, startDir 顺逆时针都可以旋转到 endDir, 但这里要求旋转的弧度 &lt; PI, 如:
    /// <code>
    /// 这里计算返回的是 false,即: 顺指针旋转
    ///   startDir
    ///     /|\
    ///      |
    ///      |
    ///      |          \
    ///      x-----------endDir
    ///                 /
    ///                 
    /// 而这里计算返回的是 true,即: 逆指针旋转
    ///             startDir
    ///               /|\
    ///                |
    ///                |
    ///       \        |
    ///  endDir--------x
    ///       /        
    /// </code>
    /// </summary>
    public static bool IsCounterClockDirection(Vector2d startDir, Vector2d endDir)
    {
        var degree = Util.AngleRadian(startDir, endDir);
        return degree >= 0;
    }
    #endregion

    #region 获取中心点 GetCenter Centroid
    /// <summary>
    /// 获取一批点的中心
    /// </summary>
    public static Vector2d GetCenter(List<Vector2d> points)
        => points == null || points.Count == 0 ? throw new Exception($"必须是合法的 点集合,才能调用 GetCenter !") : points.Aggregate((a, b) => a + b) / points.Count();

    /// <summary>
    /// 获取一批点的中心
    /// </summary>
    public static Vector3d GetCenter(List<Vector3d> points)
        => points == null || points.Count == 0 ? throw new Exception($"必须是合法的 点集合,才能调用 GetCenter !") : points.Aggregate((a, b) => a + b) / points.Count();

    /// <summary>
    /// 取多边形的质心
    /// <seealso href="https://jingsam.github.io/2016/10/05/centroid.html"/>
    /// </summary>
    public static Vector2d Centroid(List<Vector2d> points)
    {
        if (points == null || points.Count == 0) return Vector2d.Zero;
        var len = points.Count;
        if (points.First() == points.Last())
        {
            len--;
        }
        if (len == 1)
        {
            return points[0];
        }
        else if (len == 2)
        {
            return (points[0] + points[1]) / 2;
        }

        double x_sum = 0, y_sum = 0;
        for (int i = 0; i < len; ++i)
        {
            int j = (i + 1) % len;
            x_sum += (points[i].X + points[j].X) * Cross(points[i], points[j]);
            y_sum += (points[i].Y + points[j].Y) * Cross(points[i], points[j]);
        }
        var sa = GetSignedArea(points.Take(len).ToList());
        return new Vector2d { X = x_sum / 6 / sa, Y = y_sum / 6 / sa };
    }
    #endregion

    #region 点在直线上的投影 ProjectOnLine
    /// <summary>
    /// 求点 point(C) 在直线 p0(A), p1(B) 上的投影D, 原理说明如下:
    /// <code>
    ///                     C
    ///                     |
    ///                     |
    ///  A----------B * * * D
    /// 
    /// 公式:
    ///   ->   ->
    ///   AB * AC  = |AB|x|AC|xcosθ
    /// 又因为
    ///   |AD| = |AC|xcosθ
    /// 所以, 可以得到 AD 的长度
    /// so, easy...
    /// </code>
    /// </summary>
    public static Vector2d ProjectOnLine(Vector2d point, Vector2d p0, Vector2d p1)
    {
        if (p0 == p1) return p0;

        Vector2d v1 = point - p0;
        Vector2d v2 = p1 - p0;

        //var u = Util.Dot(v1, v2) / (v2.Length() * v2.Length());
        //少一次开方运算,降低精度损失
        var u = Util.Dot(v1, v2) / Util.LengthSquared(v2);
        var result = p0 + u * (p1 - p0);
        return result;
    }

    /// <inheritdoc cref="ProjectOnLine(Vector2d, Vector2d, Vector2d)"/>
    public static Vector2d ProjectOnLine(Vector2d point, LineSegment2d line)
        => ProjectOnLine(point, line.P0, line.P1);

    /// <inheritdoc cref="ProjectOnLine(Vector2d, Vector2d, Vector2d)"/>
    public static Vector3d ProjectOnLine(Vector3d point, Vector3d p0, Vector3d p1)
    {
        if (p0 == p1) return p0;

        Vector3d v1 = point - p0;
        Vector3d v2 = p1 - p0;

        //var u = Util.Dot(v1, v2) / (v2.Length() * v2.Length());
        //少一次开方运算,降低精度损失
        var u = Util.Dot(v1, v2) / Util.LengthSquared(v2);
        var result = p0 + u * (p1 - p0);
        return result;
    }

    /// <inheritdoc cref="ProjectOnLine(Vector2d, Vector2d, Vector2d)"/>
    public static Vector3d ProjectOnLine(Vector3d point, LineSegment3d line)
        => ProjectOnLine(point, line.P0, line.P1);
    #endregion

    #region 点在方向上的投影 ProjectOnVector ProjectOnVectorUnary ProjectOnVectorInfo
    /// <summary>
    /// 求点在某个方向上的投影
    /// </summary>
    /// <remarks>
    /// 注意: 传入的 <c>vector</c> 在计算前会被归一化, 所以 <c>vector</c> 的长度不会影响结果
    /// </remarks>
    public static Vector2d ProjectOnVector(Vector2d point, Vector2d vector)
    {
        if (vector == Vector2d.Zero) return Vector2d.Zero;
        //var len = Util.Dot(point, vector) / vector.Length();
        //return len * vector.Normalized();

        vector = vector.Normalized();
        return Util.Dot(point, vector) * vector;
    }

    /// <summary>
    /// 点在某个方向投影后得到的距原点的距离(可能有负值)
    /// <code>
    /// 如下: p1和p2在 x 轴上投影后分别得到 -2 和 2
    ///              /|\
    ///      p1       |       p2
    ///    (-2,2)     |      (2,2)
    ///       *       |       *
    ///       | *     |     *  |
    ///       |   *   |   *    |
    ///       |     * | *      |
    ///  -----|-------x--------|--------------------->
    ///      -2       0        2
    /// 
    /// </code>
    /// </summary>
    /// <remarks>
    /// 注意: 传入的 <c>vector</c> 在计算前可以认为被归一化, 所以 <c>vector</c> 的长度不会影响结果
    /// </remarks>
    public static double ProjectOnVectorUnary(Vector2d point, Vector2d vector)
    {
        if (vector == Vector2d.Zero) return 0;
        return Util.Dot(point, vector) / vector.Length();
    }

    /// <summary>
    /// 求点在某个方向上的投影信息, 结合 <seealso cref="Util.ProjectOnVectorUnary(Vector2d, Vector2d)"/> 和 <seealso cref="Util.ProjectOnVector(Vector2d, Vector2d)"/>
    /// <code>
    /// 如下: p1和p2在 x 轴上投影后分别得到 (-2, [-2,0]) 和 (2, [2,0])
    ///              /|\
    ///      p1       |       p2
    ///    (-2,2)     |      (2,2)
    ///       *       |       *
    ///       | *     |     *  |
    ///       |   *   |   *    |
    ///       |     * | *      |
    ///  -----|-------x--------|--------------------->
    ///      -2       0        2
    /// 
    /// </code>
    /// </summary>
    /// <remarks>
    /// 注意: 传入的 <c>vector</c> 在计算前会被归一化, 所以 <c>vector</c> 的长度不会影响结果
    /// </remarks>
    public static (double unary, Vector2d point) ProjectOnVectorInfo(Vector2d point, Vector2d vector)
    {
        if (vector == Vector2d.Zero) return (0, Vector2d.Zero);
        vector = vector.Normalized();
        var len = ProjectOnVectorUnary(point, vector);
        var project = len * vector;
        return (len, project);
    }


    /// <inheritdoc cref="ProjectOnVector(Vector2d, Vector2d)"/>
    public static Vector3d ProjectOnVector(Vector3d point, Vector3d vector)
    {
        if (vector == Vector3d.Zero) return Vector3d.Zero;
        //var len = Util.Dot(point, vector) / vector.Length();
        //return len * vector.Normalized();

        vector = vector.Normalized();
        return Util.Dot(point, vector) * vector;
    }

    /// <inheritdoc cref="ProjectOnVectorUnary(Vector2d, Vector2d)"/>
    public static double ProjectOnVectorUnary(Vector3d point, Vector3d vector)
    {
        if (vector == Vector3d.Zero) return 0;
        return Util.Dot(point, vector) / vector.Length();
    }

    /// <inheritdoc cref="ProjectOnVectorInfo(Vector2d, Vector2d)"/>
    public static (double unary, Vector3d point) ProjectOnVectorInfo(Vector3d point, Vector3d vector)
    {
        if (vector == Vector3d.Zero) return (0, Vector3d.Zero);
        vector = vector.Normalized();
        var len = ProjectOnVectorUnary(point, vector);
        var project = len * vector;
        return (len, project);
    }
    #endregion

    #region 点在线段上的投影 ProjectInSegmentParam ProjectInSegmentInfo ProjectInSegment
    /// <summary>
    /// 返回点在线段上投影的参数, 返回值情况:
    /// <list type="bullet">
    /// <item>在 [0,1] 时表示投影点在线段上</item>
    /// <item>在 (-∞,0) 时表示投影点在线段左侧</item>
    /// <item>在 (1,+∞) 时表示投影点在线段右侧</item>
    /// </list>
    /// <code>
    /// 如下, 点 point 投影的点位 proj, 那么得到的 param 表示: p0-proj / p0-p1
    /// 
    ///                      point
    ///                       |
    ///                       |
    ///           p0---------proj-----------------p1
    ///    -∞     0          0.4                  1   +∞ 
    ///                    可能是0.4
    /// </code>
    /// </summary>
    public static double ProjectInSegmentParam(Vector2d point, Vector2d p0, Vector2d p1)
    {
        if (p0 == p1) return double.NaN;
        return Util.Dot(point - p0, p1 - p0) / (p1 - p0).LengthSquared();
    }

    /// <inheritdoc cref="ProjectInSegmentParam(Vector2d, Vector2d, Vector2d)"/>
    public static double ProjectInSegmentParam(Vector2d point, LineSegment2d line)
    {
        if (line == null) return double.NaN;
        return ProjectInSegmentParam(point, line.P0, line.P1);
    }
    /// <summary>
    /// 返回点在线段上最全的投影信息:
    /// <list type="bullet">
    /// <item>param: 表示投影点在线段上的位置(小于0在左侧, 大于1在右侧, 0-1在线段上)</item>
    /// <item>proj: 未经修正的投影点, 可能在线段外</item>
    /// <item>fixProj: 修正后的投影点, 肯定在线段上</item>
    /// </list>
    /// <code>
    /// 如下, 点 point 投影的点位 proj, 但在线段左侧, 修正后为 p0, 所以可能的返回值是(-0.4, proj, p0)
    /// 
    ///           point
    ///            |
    ///            |
    ///           proj * * * * p0-----------------p1
    ///                     fixProj
    /// </code>
    /// </summary>
    public static (double param, Vector2d proj, Vector2d fixProj) ProjectInSegmentInfo(Vector2d point, Vector2d p0, Vector2d p1)
    {
        var param = ProjectInSegmentParam(point, p0, p1);
        Vector2d proj, fixProj;
        proj = param * (p1 - p0) + p0;
        if (param <= 0) fixProj = p0;
        else if (param >= 1) fixProj = p1;
        else fixProj = proj;
        return (param, proj, fixProj);
    }

    /// <inheritdoc cref="ProjectInSegmentInfo(Vector2d, Vector2d, Vector2d)"/>
    public static (double param, Vector2d proj, Vector2d fixProj) ProjectInSegmentInfo(Vector2d point, LineSegment2d line)
        => ProjectInSegmentInfo(point, line.P0, line.P1);

    /// <summary>
    /// 求点 point 在线段 p0,p1 上的投影, 原理同 <seealso cref="ProjectOnLine(Vector2d, Vector2d, Vector2d)"/>
    /// <code>
    ///          
    /// //下面点 point 投影得到 proj 与 p1 重合
    ///                        point
    ///                         *
    ///                       *  
    ///                     *
    /// p0---------------p1
    ///                 proj
    /// </code>
    /// </summary>
    /// <remarks>
    /// 注意: 点 point 的投影不可能超出线段端点
    /// </remarks>
    public static Vector2d ProjectInSegment(Vector2d point, Vector2d p0, Vector2d p1)
    {
        if (p1 == p0) return p0;
        var k = Util.Dot(point - p0, p1 - p0) / (p1 - p0).LengthSquared();
        if (k < 0) k = 0;
        if (k > 1) k = 1;
        return k * (p1 - p0) + p0;
    }

    /// <inheritdoc cref="ProjectInSegment(Vector2d, Vector2d, Vector2d)"/>
    public static Vector2d ProjectInSegment(Vector2d point, LineSegment2d line)
    {
        if (line == null) return Vector2d.Zero;
        return ProjectInSegment(point, line.P0, line.P1);
    }

    /// <inheritdoc cref="ProjectInSegment(Vector2d, Vector2d, Vector2d)"/>
    public static Vector3d ProjectInSegment(Vector3d point, Vector3d p0, Vector3d p1)
    {
        if (p1 == p0) return p0;
        var k = Util.Dot(point - p0, p1 - p0) / (p1 - p0).LengthSquared();
        if (k < 0) k = 0;
        if (k > 1) k = 1;
        return k * (p1 - p0) + p0;
    }

    /// <inheritdoc cref="ProjectInSegment(Vector2d, Vector2d, Vector2d)"/>
    public static Vector3d ProjectInSegment(Vector3d point, LineSegment3d line)
    {
        if (line == null) return Vector3d.Zero;
        return ProjectInSegment(point, line.P0, line.P1);
    }
    #endregion

    #region 线段投影到直线 ProjectLineSegmentOnLine
    /// <summary>
    /// 将线段投影到直线上
    /// </summary>
    /// <remarks>注意: 返回新的线段, 老的线段不变</remarks>
    public static LineSegment2d ProjectLineSegmentOnLine(LineSegment2d lineSegment, LineSegment2d line)
    {
        if (lineSegment == null || line == null) return lineSegment;
        var proj_2_0 = Util.ProjectOnLine(lineSegment.P0, line.P0, line.P1);
        var proj_2_1 = Util.ProjectOnLine(lineSegment.P1, line.P0, line.P1);
        return new LineSegment2d(proj_2_0, proj_2_1);
    }
    #endregion

    #region 三维点投影到面 ProjectOnPlane
    /// <summary>
    /// 求点在某个面上的投影
    /// </summary>
    public static Vector3d ProjectOnPlane(Vector3d point, List<Vector3d> points)
    {
        if (points == null || points.Count < 3) return Vector3d.Zero;
        if (points.Last() == points.First()) points = points.SkipLast(1).ToList();
        if (points.Count < 3) return Vector3d.Zero;
        var normal = GetPolygonNormal(points);
        var center = GetCenter(points);
        var v = (center - point);
        var d = Dot(v, normal);
        return point + d * normal;
    }
    #endregion

    #region 射线与线段相交 IntersectRayAndLineSegment
    /// <summary>
    /// 射线与线段相交
    /// 注意: 如果射线与线段平行 则不相交
    /// </summary>
    public static Vector2d? IntersectRayAndLineSegment(Ray2d ray, LineSegment2d lineSegment, double tolerance = 0.0001)
    {
        var p = Util.IntersectLineAndLine(new LineSegment2d(ray.Origin, ray.Origin + ray.Direction * 10), lineSegment);
        if (!Util.IsNearlyPointOnLineSegment(p, lineSegment, tolerance)) return null;
        if (Util.IsNearlySameDirection(ray.Direction, (p - ray.Origin))) return p;
        return null;
    }

    /// <summary>
    /// 求射线和一批线段交点, 返回交点集合 按距离射线原点从近都远排列
    /// </summary>
    public static List<Vector2d> IntersectRayAndLineSegments(Ray2d ray, List<LineSegment2d> lineSegments, double tolerance = 0.0001)
    {
        var ps = lineSegments.Select(i => Util.IntersectRayAndLineSegment(ray, i, tolerance))
            .Where(i => i != null)
            .Select(i => i!.Value).ToList();
        if (ps.Count == 0) return new List<Vector2d>();
        return ps.OrderBy(i => (i - ray.Origin).Length()).ToList();
    }

    /// <summary>
    /// 求射线和一批线段交点, 返回交点和线段集合 按距离射线原点从近都远排列
    /// </summary>
    public static List<(Vector2d cross, LineSegment2d lineSegment)> IntersectRayAndLineSegmentsInfo(Ray2d ray, List<LineSegment2d> lineSegments, double tolerance = 0.0001)
    {
        var ps = lineSegments.Select(i => (Util.IntersectRayAndLineSegment(ray, i, tolerance), i))
            .Where(i => i.Item1 != null)
            .Select(i => (i.Item1!.Value, i.Item2))
            .ToList();
        if (ps.Count == 0) return new List<(Vector2d cross, LineSegment2d)>();
        return ps.OrderBy(i => (i.Item1 - ray.Origin).Length()).ToList();
    }
    #endregion

    #region 点线关系
    /// <summary>
    /// 计算点和线段的关系, 注意: tolerance 表示: 当点 point 在 tolerance 距离内吸附到线段上或线段端点上<br/>
    /// </summary>
    public static PointWithLineSegmentResult CalculatePointWithLineSegment(Vector2d point, Vector2d p0, Vector2d p1, double tolerance = 0.0001)
    {
        //检查数据
        if (p0 == p1)
        {
            if (IsNearlySame(point, p0, tolerance))
                return new PointWithLineSegmentResult
                {
                    Flag = EnumPointWithLineSegment.IsOnCorner,
                    CrossPoint = p0,
                    PointIndex = 0,
                };
            else
                return new PointWithLineSegmentResult
                {
                    Flag = EnumPointWithLineSegment.IsOut,
                    CrossPoint = Vector2d.Zero,
                    PointIndex = 0,
                };
        }
        //判断点是否在线段的端点上
        if (IsNearlySame(point, p0, tolerance))
        {
            return new PointWithLineSegmentResult
            {
                Flag = EnumPointWithLineSegment.IsOnCorner,
                CrossPoint = p0,
                PointIndex = 0,
            };
        }
        if (IsNearlySame(point, p1, tolerance))
        {
            return new PointWithLineSegmentResult
            {
                Flag = EnumPointWithLineSegment.IsOnCorner,
                CrossPoint = p1,
                PointIndex = 1,
            };
        }
        //点距离线段的哪个端点更近
        var idx = 0;
        if ((point - p0).Length() > (point - p1).Length()) idx = 1;
        //判断点是否在线上
        if (IsNearlyPointOnLineSegment(point, new LineSegment2d(p0, p1), tolerance))
        {
            return new PointWithLineSegmentResult
            {
                Flag = EnumPointWithLineSegment.IsOnEdge,
                CrossPoint = ProjectInSegment(point, p0, p1),
                PointIndex = idx,
            };
        }
        //判断点是否在线段的延长线上
        if (IsNearlySameLine(point, p0, p1, tolerance))
        {
            return new PointWithLineSegmentResult
            {
                Flag = EnumPointWithLineSegment.IsOnExtensionLine | EnumPointWithLineSegment.IsOut,
                CrossPoint = ProjectOnLine(point, p0, p1),
                PointIndex = idx,
            };
        }

        //点在线外, 且不是线段延长线上
        return new PointWithLineSegmentResult
        {
            Flag = EnumPointWithLineSegment.IsOut,
            CrossPoint = ProjectOnLine(point, p0, p1),
            PointIndex = idx,
        };
    }
    /// <summary>
    /// 判断点 point2/point3 是否在 origin-dir 的两侧
    /// </summary>
    public static bool IsNearlyPointAsideLine(Vector2d origin, Vector2d dir, Vector2d point2, Vector2d point3, double degreeTolerance = 1)
    {
        var degree = dir.AngleRadian().ToDegree();
        var degree2 = (point2 - origin).AngleRadian().ToDegree();
        var degree3 = (point3 - origin).AngleRadian().ToDegree();
        if (degree.IsNearlySame(degree2, degreeTolerance) || degree.IsNearlySame(degree3, degreeTolerance))
            return false;

        if (degree > degree2 && degree < degree3) return true;
        if (degree > degree3 && degree < degree2) return true;
        return false;
    }

    /// <summary>
    /// 判断点P是否在线段AB上, 原理是: 点P向线段AB的投影点是C, PC的距离小于tolerance<br/>
    /// <code>
    ///              P
    ///              |
    /// A------------C-------------B
    /// </code>
    /// </summary>
    public static bool IsNearlyPointOnLineSegment(Vector3d point, LineSegment3d lineSegment, double tolerance = 0.0001)
    {
        if (lineSegment == null) return false;
        var project = ProjectInSegment(point, lineSegment.P0, lineSegment.P1);
        return Math.Abs(project.DistanceTo(point)) <= tolerance;
    }
    /// <summary>
    /// 判断点P是否在线段AB上, 原理是: 点P向线段AB的投影点是C, PC的距离小于tolerance
    /// <code>
    ///              P
    ///              |
    /// A------------C-------------B
    /// </code>
    /// </summary>
    public static bool IsNearlyPointOnLineSegment(Vector2d point, LineSegment2d lineSegment, double tolerance = 0.0001)
    {
        if (lineSegment == null) return false;
        return IsNearlyPointOnLineSegment(point, lineSegment.P0, lineSegment.P1);
    }

    /// <summary>
    /// 判断点P是否在线段AB上, 原理是: 点P向线段AB的投影点是C, PC的距离小于tolerance
    /// <code>
    ///              P
    ///              |
    /// A------------C-------------B
    /// </code>
    /// </summary>
    public static bool IsNearlyPointOnLineSegment(Vector2d point, Vector2d line_p0, Vector2d line_p1, double tolerance = 0.0001)
    {
        var project = ProjectInSegment(point, line_p0, line_p1);
        return Math.Abs(project.DistanceTo(point)) <= tolerance;
    }
    /// <summary>
    /// 点到线的距离, 点先投影到线, 然后再求点和投影间的距离
    /// </summary>
    /// <remarks>注意: 不是线段</remarks>
    public static double DistanceToLine(Vector2d point, LineSegment2d line)
    {
        var project = Util.ProjectOnLine(point, line.P0, line.P1);
        return point.DistanceTo(project);
    }
    /// <summary>
    /// 判断点是否在线上
    /// </summary>
    /// <remarks>
    /// 注意: 区分 <seealso cref="Util.IsNearlyPointOnLineSegment(Vector2d, LineSegment2d, double)"/>
    /// </remarks>
    public static bool IsNearlyPointOnLine(Vector2d point, Vector2d p0, Vector2d p1, double tolerance = 0.0001)
    {
        var p = ProjectOnLine(point, p0, p1);
        return (p - point).Length() < tolerance;
    }
    /// <summary>
    /// 点到线段的距离, 点先投影到线段, 然后再求点和投影间的距离
    /// </summary>
    public static double DistanceToLineSegment(Vector2d point, LineSegment2d lineSegment)
    {
        var project = Util.ProjectInSegment(point, lineSegment);
        return point.DistanceTo(project);
    }
    #endregion

    #region 点与多边形关系
    /// <summary>
    /// 计算点和面的关系, 注意: tolerance 表示: 当点 point 在 tolerance 距离内吸附到多边形 polygon 的边或顶点上<br/><br/>
    /// 核心算法采用 clipper2: <seealso href="https://github.com/AngusJohnson/Clipper2/blob/Clipper2_1.3.0/CSharp/Clipper2Lib/Clipper.Core.cs#L703"/><br/>
    /// 算法理解: 本质上是射线法, 向x轴负方向做射线, 如果与 polygon 边的交点是偶数, 则在多边形外, 奇数则在多边形内<br/>
    /// 代码示例:
    /// <code>
    /// // 2-------1
    /// // |       |
    /// // |   .   |
    /// // |       |
    /// // 3-------0
    /// var point = new Vector2d(0, 0);
    /// var polygon = new List&lt;Vector2d>
    ///     {
    ///         new Vector2d(1,-1),
    ///         new Vector2d(1,1),
    ///         new Vector2d(-1,1),
    ///         new Vector2d(-1,-1),
    ///     };
    /// var result = Util.CalculatePointWithPolygon(point, polygon);
    /// result.IsInside().ShouldBe(true);
    /// </code>
    /// </summary>
    public static PointWithPolygonResult CalculatePointWithPolygon(Vector2d point, List<Vector2d> polygon, double tolerance = 0.0001)
    {
        var outsideResult = new PointWithPolygonResult { Flag = EnumPointWithPolygon.IsOutside };
        var insideResult = new PointWithPolygonResult { Flag = EnumPointWithPolygon.IsInside };
        if (polygon == null || polygon.Count == 0)
            return outsideResult;
        int len = polygon.Count, start = 0;
        if (polygon.Last() == polygon.First()) len--;
        if (len < 3) return outsideResult;

        //先计算是否在顶点上
        for (int j = 0; j < len; j++)
        {
            if (polygon[j].IsNearlySame(point, tolerance))
            {
                return new PointWithPolygonResult
                {
                    Flag = EnumPointWithPolygon.IsOnCorner,
                    CrossPoint = polygon[j],
                    PointIndex = j,
                };
            }
        }
        //再计算是否在边上
        for (int j = 0; j < len; j++)
        {
            if (IsNearlyPointOnLineSegment(point, new LineSegment2d(polygon[j], polygon[(j + 1) % len]), tolerance))
            {
                var crossPoint = ProjectOnLine(point, polygon[j], polygon[(j + 1) % len]);
                return new PointWithPolygonResult
                {
                    Flag = EnumPointWithPolygon.IsOnEdge,
                    CrossPoint = crossPoint,
                    PointIndex = j,
                };
            }
        }

        //最后判断点在面内还是面外
        //先在 polygon 上找一个和 point 不同高度的点
        while (start < len && polygon[start].Y == point.Y) start++;
        if (start == len) return outsideResult;

        double d;
        //通过判断连续的两个点分别在 point 的上方和下方, 判定射线有没有可能与这个边相交
        //需要进一步判断是否相交在x轴负方向上
        //isAbove: 遍历polygon点时, point 是否在当前点的上方
        //startingAbove: point 是否在遍历起始点的上方
        bool isAbove = polygon[start].Y < point.Y, startingAbove = isAbove;
        //表示与x轴负方向射线交点个数奇偶
        int val = 0, i = start + 1, end = len;
        while (true)
        {
            //循环的时候分两段, 如: polygon 有5(索引是:0,1,2,3,4)个点位, 可能从索引2开始,则分成两段 [2,3,4]/[0,1]
            if (i == end)
            {
                //遍历结束
                if (end == 0 || start == 0) break;
                //开启下一段遍历
                end = start;
                i = 0;
            }

            if (isAbove)
            {
                //当前点在 point 上方, 找一个不在上方的
                while (i < end && polygon[i].Y < point.Y) i++;
                //从下一段再找
                if (i == end) continue;
            }
            else
            {
                //当前点在 point 下方, 找一个不在下方的
                while (i < end && polygon[i].Y > point.Y) i++;
                //从下一段再找
                if (i == end) continue;
            }

            Vector2d curr = polygon[i], prev;
            if (i > 0) prev = polygon[i - 1];
            else prev = polygon[len - 1];

            if (curr.Y == point.Y)
            {
                //由前面判断知: 点不在面上, 所以不用像clipper2源码一样, 直接接着遍历或结束
                i++;
                if (i == start) break;
                continue;
            }

            if (point.X < curr.X && point.X < prev.X)
            {
                // we're only interested in edges crossing on the left
            }
            else if (point.X > prev.X && point.X > curr.X)
            {
                //肯定与x轴负方向射线相交
                /*
                 *    pre
                 *    |
                 *    |  point
                 *    |
                 *    cur
                 */
                val = 1 - val; // toggle val
            }
            else
            {
                //也与x轴负方向相交
                /* 
                 * 示例场景: isAbove=false, 向量1(pre->cur)与向量2(cur->point)外积>0
                 * pre
                 *  \
                 *   \ point
                 *    \  |
                 *     cur
                 */
                d = Cross(curr - prev, point - curr);
                if ((d < 0) == isAbove) val = 1 - val;
            }
            isAbove = !isAbove;
            i++;
        }

        if (isAbove != startingAbove)
        {
            //遍历终点和起始点分布在 point 的上下两方, 在进行一次射线判断,和上面的判断一个意思
            if (i == len) i = 0;
            if (i == 0)
                d = Cross(polygon[0] - polygon[len - 1], point - polygon[0]);
            else
                d = Cross(polygon[i] - polygon[i - 1], point - polygon[i]);
            if ((d < 0) == isAbove) val = 1 - val;
        }

        //交点偶数在 polygon 外面,否则在 polygon 里面
        if (val == 0)
            return outsideResult;
        return insideResult;
    }
    /// <summary>
    /// 点是否在多边形内, 注意: 在边或顶点上不算
    /// </summary>
    public static bool IsPointInPolygon(Vector2d point, List<Vector2d> poly, double tolerance = 0.0001)
    {
        return Util.CalculatePointWithPolygon(point, poly, tolerance).IsInside();
    }

    /// <summary>
    /// 点是否在多边形上, 注意: 包含在边或顶点上
    /// </summary>
    public static bool IsPointOnPolygon(Vector2d point, List<Vector2d> poly, double tolerance = 0.0001)
    {
        return Util.CalculatePointWithPolygon(point, poly, tolerance).IsOn();
    }

    /// <summary>
    /// 点是否在多边形外, 注意: 在边或顶点上不算
    /// </summary>
    public static bool IsPointOutPolygon(Vector2d point, List<Vector2d> poly, double tolerance = 0.0001)
    {
        return Util.CalculatePointWithPolygon(point, poly, tolerance).IsOutside();
    }
    #endregion

    #region 线线关系
    /// <summary>
    /// 求两条直线的交点, 注意: 重合的直线认为没有交点, 所以需要先行判断两条直线是否平行
    /// </summary>
    public static Vector2d IntersectLineAndLine(LineSegment2d line1, LineSegment2d line2)
    {
        Vector2d line1_p0 = line1.P0, line1_p1 = line1.P1, line2_p0 = line2.P0, line2_p1 = line2.P1;
        if (IsNearlyParallel(new LineSegment2d(line1_p0, line1_p1), new LineSegment2d(line2_p0, line2_p1), 0))
            return Vector2d.Zero;
        double x1, x2, y1, y2;
        //直线1: a1*x+b1*y+C = 0
        x1 = line1_p0.X;
        x2 = line1_p1.X;
        y1 = line1_p0.Y;
        y2 = line1_p1.Y;
        double a1 = y2 - y1;
        double b1 = x1 - x2;
        double c1 = x2 * y1 - x1 * y2;
        //直线2: a2*x+b2*y+c=0
        x1 = line2_p0.X;
        x2 = line2_p1.X;
        y1 = line2_p0.Y;
        y2 = line2_p1.Y;
        double a2 = y2 - y1;
        double b2 = x1 - x2;
        double c2 = x2 * y1 - x1 * y2;

        //先判断是否平行
        var divide = a1 * b2 - a2 * b1;
        if (divide == 0) return Vector2d.Zero;
        //求得交点 (x,y)
        var y = (c1 * a2 - c2 * a1) / divide;
        var x = (c2 * b1 - c1 * b2) / divide;
        return new Vector2d { X = x, Y = y };
    }
    /// <summary>
    /// 计算两条线段的交点, 最多有两个交点
    /// </summary>
    public static List<Vector2d> IntersectLineSegmentAndLineSegment(LineSegment2d line1, LineSegment2d line2, double tolerance = 0.0001)
    {
        if (line1 == null || line2 == null || line1.P0 == line1.P1 || line2.P0 == line2.P1) return [];
        var res = new List<Vector2d>();
        if (line1.IsNearlyParallel(line2, 0))
        {
            //平行的相交
            if (line1.P0.IsNearlyOnLineSegment(line2, 0)) res.Add(line1.P0);
            if (line1.P1.IsNearlyOnLineSegment(line2, 0)) res.Add(line1.P1);

            if (line2.P0.IsNearlyOnLineSegment(line1, 0)) res.Add(line2.P0);
            if (line2.P1.IsNearlyOnLineSegment(line1, 0)) res.Add(line2.P1);
            return res.Distinct().ToList();
        }
        else
        {
            //非平行
            var p = IntersectLineAndLine(line1, line2);
            if (p.IsNearlyOnLineSegment(line1, tolerance) && p.IsNearlyOnLineSegment(line2, tolerance)) res.Add(p);
        }
        return res;
    }
    /// <summary>
    /// 判断两线段是否近似平行, 两直线夹角在 degreeTolerance 范围内
    /// </summary>
    public static bool IsNearlyParallel(LineSegment2d line, LineSegment2d line2, double degreeTolerance = 1)
    {
        if (line == null || line2 == null) return false;
        var angle = line.AngleRadian(line2).ToDegree();
        return angle <= degreeTolerance;
    }

    /// <summary>
    /// 判断两线段是否近似垂直, 两直线夹角与 90° 的差在 degreeTolerance 范围内
    /// </summary>
    public static bool IsNearlyPerpendicular(LineSegment2d line, LineSegment2d line2, double degreeTolerance = 1)
    {
        if (line == null || line2 == null) return false;
        var angle = line.AngleRadian(line2);
        return Math.Abs(angle - Math.PI / 2).ToDegree() <= degreeTolerance;
    }
    /// <summary>
    /// 判断两条线段是否近似相交(有重合的点即认为是相交)<br/>
    /// 原理: 跨立实验 <seealso href="https://zhuanlan.zhihu.com/p/624057141"/>
    /// </summary>
    public static bool IsNearyLineSegmentIntersect(LineSegment2d line1, LineSegment2d line2, double tolerance = 0.0001)
    {
        if (line1 == null || line2 == null) return false;
        return IsNearyLineSegmentIntersect(line1.P0, line1.P1, line2.P0, line2.P1, tolerance);
    }

    /// <summary>
    /// 判断两条线段是否近似相交(有重合的点即认为是相交)<br/>
    /// 原理: 跨立实验 <seealso href="https://zhuanlan.zhihu.com/p/624057141"/>
    /// </summary>
    public static bool IsNearyLineSegmentIntersect(Vector2d line1_p0, Vector2d line1_p1, Vector2d line2_p0, Vector2d line2_p1, double tolerance = 0.0001)
    {
        //边界判断: 相接或重合
        if (IsNearlyPointOnLineSegment(line1_p0, line2_p0, line2_p1, tolerance) || IsNearlyPointOnLineSegment(line1_p1, line2_p0, line2_p1, tolerance)
            || IsNearlyPointOnLineSegment(line2_p0, line1_p0, line1_p1, tolerance) || IsNearlyPointOnLineSegment(line2_p1, line1_p0, line1_p1, tolerance))
            return true;
        //跨立实验: 满足下面两个条件即可
        //1. CA CB 在CD的两侧
        //2. AC AD 在AB的两侧

        /*
         * AB: line1, CD: line2
         *                  C
         *                  |
         *                  |
         * A----------------|----------B
         *                  |
         *                  D
         * 
         */
        double flag1, flag2;
        Vector2d a = line1_p0, b = line1_p1, c = line2_p0, d = line2_p1;
        var ca = a - c;
        var cb = b - c;
        var cd = d - c;
        flag1 = Util.Cross(ca, cd);
        flag2 = Util.Cross(cb, cd);
        if (flag1 * flag2 > 0) return false;

        var ac = c - a;
        var ad = d - a;
        var ab = b - a;
        flag1 = Util.Cross(ac, ab);
        flag2 = Util.Cross(ad, ab);
        if (flag1 * flag2 > 0) return false;
        return true;
    }
    /// <summary>
    /// 判断两条线段是否有重叠部分
    /// </summary>
    public static bool IsNearlyOverlap(LineSegment2d line1, LineSegment2d line2, double minOverlapLength, double tolerance = 0.0001)
    {
        if (line1 == null || line2 == null) return false;
        //先将 line2 的两个点投影到 line1 上
        var vector = line1.Direction();
        var proj_2_0 = Util.ProjectOnLine(line2.P0, line1.P0, line1.P1);
        if (proj_2_0.DistanceTo(line2.P0) > tolerance) return false;
        var proj_2_1 = Util.ProjectOnLine(line2.P1, line1.P0, line1.P1);
        if (proj_2_1.DistanceTo(line2.P1) > tolerance) return false;

        var unary1_0 = 0d;
        var unary1_1 = line1.Length();
        var unary2_0 = proj_2_0.DistanceTo(line1.P0);
        if (!Util.IsNearlySameDirection(proj_2_0 - line1.P0, vector, 1)) unary2_0 = -unary2_0;
        var unary2_1 = proj_2_1.DistanceTo(line1.P0);
        if (!Util.IsNearlySameDirection(proj_2_1 - line1.P0, vector, 1)) unary2_1 = -unary2_1;

        var min1 = Math.Min(unary1_0, unary1_1);
        var max1 = Math.Max(unary1_0, unary1_1);
        var min2 = Math.Min(unary2_0, unary2_1);
        var max2 = Math.Max(unary2_0, unary2_1);

        if (max1 > min2 && max2 > min1)
        {
            // min1---------min2--------max1-----max2
            // min2---------min1--------max2-----max1
            return Math.Min(max1 - min2, max2 - min1) > minOverlapLength;
        }
        return false;
    }

    /// <summary>
    /// 判断线段1是否包含线段2
    /// </summary>
    public static bool IsNearlyContains(LineSegment2d line1, LineSegment2d line2, double tolerance = 0.0001)
    {
        if (line1 == null || line2 == null) return false;
        //先将 line2 的两个点投影到 line1 上
        var vector = line1.Direction();
        var proj_2_0 = Util.ProjectOnLine(line2.P0, line1.P0, line1.P1);
        if (proj_2_0.DistanceTo(line2.P0) > tolerance) return false;
        var proj_2_1 = Util.ProjectOnLine(line2.P1, line1.P0, line1.P1);
        if (proj_2_1.DistanceTo(line2.P1) > tolerance) return false;

        var unary1_0 = 0d;
        var unary1_1 = line1.Length();
        var unary2_0 = proj_2_0.DistanceTo(line1.P0);
        if (!Util.IsNearlySameDirection(proj_2_0 - line1.P0, vector, 1)) unary2_0 = -unary2_0;
        var unary2_1 = proj_2_1.DistanceTo(line1.P0);
        if (!Util.IsNearlySameDirection(proj_2_1 - line1.P0, vector, 1)) unary2_1 = -unary2_1;

        var min1 = Math.Min(unary1_0, unary1_1);
        var max1 = Math.Max(unary1_0, unary1_1);
        var min2 = Math.Min(unary2_0, unary2_1);
        var max2 = Math.Max(unary2_0, unary2_1);

        return max1 + tolerance > max2 && min1 - tolerance < min2;
    }

    /// <summary>
    /// 两个线段重叠的长度
    /// </summary>
    public static double OverlapLength(LineSegment2d line1, LineSegment2d line2, double tolerance = 0.0001)
    {
        if (!Util.IsNearlyParallel(line1, line2, 1d.ToRadian())) return 0;
        var line1_p0_in_line2 = Util.IsNearlyPointOnLineSegment(line1.P0, line2, tolerance);
        var line1_p1_in_line2 = Util.IsNearlyPointOnLineSegment(line1.P1, line2, tolerance);
        var line2_p0_in_line1 = Util.IsNearlyPointOnLineSegment(line2.P0, line1, tolerance);
        var line2_p1_in_line1 = Util.IsNearlyPointOnLineSegment(line2.P1, line1, tolerance);
        if (line1_p0_in_line2 && line1_p1_in_line2)
        {
            // line2 包含 line1
            return line1.Length();
        }
        if (line2_p0_in_line1 && line2_p1_in_line1)
        {
            // line1 包含 line2
            return line2.Length();
        }
        if ((line1_p0_in_line2 || line1_p1_in_line2) && (line2_p0_in_line1 || line2_p1_in_line1))
        {
            var p_line1 = line1_p0_in_line2 ? line1.P0 : line1.P1;
            var p_line2 = line2_p0_in_line1 ? line2.P0 : line2.P1;
            return p_line1.DistanceTo(p_line2);
        }
        return 0;
    }

    /// <summary>
    /// 两个线段在某个方向上重叠的长度
    /// </summary>
    public static double OverlapLengthOnVector(LineSegment2d line1, LineSegment2d line2, Vector2d dir, double tolerance = 0.0001)
    {
        line1 = new LineSegment2d(Util.ProjectOnVector(line1.P0, dir), Util.ProjectOnVector(line1.P1, dir));
        line2 = new LineSegment2d(Util.ProjectOnVector(line2.P0, dir), Util.ProjectOnVector(line2.P1, dir));
        return Util.OverlapLength(line1, line2, tolerance);
    }

    /// <summary>
    /// 两个线段是否包含
    /// </summary>
    public static bool IsContains(LineSegment2d shortLine, LineSegment2d longLine, double tolerance = 0.0001)
    {
        if (!Util.IsNearlyParallel(shortLine, longLine, 1d.ToRadian())) return false;
        var line1_p0_in_line2 = Util.IsNearlyPointOnLineSegment(shortLine.P0, longLine, tolerance);
        var line1_p1_in_line2 = Util.IsNearlyPointOnLineSegment(shortLine.P1, longLine, tolerance);
        if (line1_p0_in_line2 && line1_p1_in_line2) return true;
        return false;
    }

    /// <summary>
    /// 两个线段在指定方向上是否包含
    /// </summary>
    public static bool IsContainsOnVector(LineSegment2d shortLine, LineSegment2d longLine, Vector2d dir, double tolerance = 0.0001)
    {
        shortLine = new LineSegment2d(Util.ProjectOnVector(shortLine.P0, dir), Util.ProjectOnVector(shortLine.P1, dir));
        longLine = new LineSegment2d(Util.ProjectOnVector(longLine.P0, dir), Util.ProjectOnVector(longLine.P1, dir));
        return IsContains(shortLine, longLine, tolerance);
    }
    #endregion

    #region 线与多边形关系
    /// <summary>
    /// 线段是否完全多边形内(不能与边有任何交点), 注意: tolerance 表示: 当点 point 在 tolerance 距离内吸附到多边形 polygon 的边或顶点上<br/>
    /// 效果如下:
    /// <code>
    /// 完全在内部: true 
    /// x--------x      
    /// |        |      
    /// | p0--p1 |      
    /// |        |      
    /// x--------x      
    ///   
    /// 相交: false      与边有交点: false     甚至与边重叠: false
    /// x--------x      x--------x           x--------x
    /// |        |      |        |           |        |
    /// | p0-----|--p1  |       p0--p1       |        p0
    /// |        |      |        |           |        |
    /// x--------x      x--------x           x--------x 
    ///                                               |
    ///                                               p1
    /// 
    /// </code>
    /// </summary>
    public static bool IsLineSegmentInPolygon(LineSegment2d line, List<Vector2d> polygon, double tolerance = 0.0001)
    {
        if (line == null) return false;
        if (polygon == null || polygon.Count < 3) return false;
        //兼容封闭的线
        if (polygon.First() == polygon.Last()) polygon = polygon.SkipLast(1).ToList();
        if (polygon.Count < 3) return false;
        //两个点都在多边形内 且 不与任意边相交即可
        var res1 = Util.CalculatePointWithPolygon(line.P0, polygon, tolerance);
        if (!res1.IsInside()) return false;

        var res2 = Util.CalculatePointWithPolygon(line.P1, polygon, tolerance);
        if (!res2.IsInside()) return false;

        //不能相交
        for (int i = 0; i < polygon.Count; i++)
        {
            var cur = polygon[i];
            var nxt = polygon[(i + 1) % polygon.Count];
            if (Util.IsNearyLineSegmentIntersect(line.P0, line.P1, cur, nxt, tolerance)) return false;
        }
        return true;
    }

    /// <summary>
    /// 线段是否与多边形相交(只要有交点即可), 注意: tolerance 表示: 当点 point 在 tolerance 距离内吸附到多边形 polygon 的边或顶点上<br/>
    /// 效果如下:
    /// <code>
    ///   一般相交: true       与边有交点: true     甚至与边重叠: true
    ///  x--------x            x--------x           x--------x     
    ///  |        |            |        |           |        |     
    ///  | p0-----|--p1        |       p0--p1       |        p0    
    ///  |        |            |        |           |        |     
    ///  x--------x            x--------x           x--------x     
    ///                                                      |     
    ///                                                      p1   
    /// 
    ///                 
    ///  完全在内部: false    完全在外部: false
    ///   x--------x         x--------x     
    ///   |        |         |        |     
    ///   | p0--p1 |         |        |  p0--p1
    ///   |        |         |        |     
    ///   x--------x         x--------x     
    ///                      
    ///                      
    /// 
    /// </code>
    /// </summary>
    public static bool IsLineSegmentIntersectPolygon(LineSegment2d line, List<Vector2d> polygon, double tolerance = 0.0001)
    {
        if (line == null) return false;
        if (polygon == null || polygon.Count < 3) return false;
        //兼容封闭的线
        if (polygon.First() == polygon.Last()) polygon = polygon.SkipLast(1).ToList();
        if (polygon.Count < 3) return false;

        for (int i = 0; i < polygon.Count; i++)
        {
            var cur = polygon[i];
            var nxt = polygon[(i + 1) % polygon.Count];
            if (Util.IsNearyLineSegmentIntersect(line.P0, line.P1, cur, nxt, tolerance)) return true;
        }
        return false;
    }

    /// <summary>
    /// 线段是否完全在多边形外(不能有任何交点或在内部), 注意: tolerance 表示: 当点 point 在 tolerance 距离内吸附到多边形 polygon 的边或顶点上<br/>
    /// 效果如下:
    /// <code>
    ///  完全在外部: true         
    ///  x--------x                
    ///  |        |                
    ///  |        |  p0--p1           
    ///  |        |                
    ///  x--------x                
    ///                              
    ///   相交: false      甚至与边重叠: false    完全在内部: false     
    ///  x--------x            x--------x          x--------x   
    ///  |        |            |        |          |        |   
    ///  | p0-----|--p1        |        p0         | p0--p1 |   
    ///  |        |            |        |          |        |   
    ///  x--------x            x--------x          x--------x   
    ///                                 |                       
    ///                                p1                       
    /// </code>
    /// </summary>
    public static bool IsLineSegmentOutsidePolygon(LineSegment2d line, List<Vector2d> polygon, double tolerance = 0.0001)
    {
        if (line == null) return false;
        if (polygon == null || polygon.Count < 3) return false;
        //兼容封闭的线
        if (polygon.First() == polygon.Last()) polygon = polygon.SkipLast(1).ToList();
        if (polygon.Count < 3) return false;

        //两个点都在多边形内 且 不与任意边相交即可
        var res1 = Util.CalculatePointWithPolygon(line.P0, polygon, tolerance);
        if (!res1.IsOutside()) return false;

        var res2 = Util.CalculatePointWithPolygon(line.P1, polygon, tolerance);
        if (!res2.IsOutside()) return false;

        for (int i = 0; i < polygon.Count; i++)
        {
            var cur = polygon[i];
            var nxt = polygon[(i + 1) % polygon.Count];
            if (Util.IsNearyLineSegmentIntersect(line.P0, line.P1, cur, nxt, tolerance)) return false;
        }
        return true;
    }

    /// <summary>
    /// 线段是否在多边形上(线段要被多边形的一条边包含), 注意: tolerance 表示: 当点 point 在 tolerance 距离内吸附到多边形 polygon 的边或顶点上<br/>
    /// </summary>
    public static bool IsLineSegmentOnPolygon(LineSegment2d line, List<Vector2d> polygon, double tolerance = 0.0001)
    {
        if (line == null) return false;
        if (polygon == null || polygon.Count < 3) return false;
        //兼容封闭的线
        if (polygon.First() == polygon.Last()) polygon = polygon.SkipLast(1).ToList();
        if (polygon.Count < 3) return false;

        for (int i = 0; i < polygon.Count; i++)
        {
            var cur = polygon[i];
            var nxt = polygon[(i + 1) % polygon.Count];
            if (Util.IsNearlyPointOnLineSegment(line.P0, cur, nxt, tolerance) && Util.IsNearlyPointOnLineSegment(line.P1, cur, nxt, tolerance)) return true;
        }
        return false;
    }
    /// <summary>
    /// 不相交的多边形到直线的距离, 即: 多边形所有的点到直线的距离中最小的一个<br/>
    /// </summary>
    public static double DistanceToLine(List<Vector2d> poly, LineSegment2d lineSegment)
    {
        var minLen = double.MaxValue;
        for (int i = 0; i < poly.Count; i++)
        {
            var p = poly[i];
            var len = Util.DistanceToLine(p, lineSegment);
            minLen = Math.Min(minLen, len);
        }
        return minLen;
    }
    /// <summary>
    /// 计算线段和多边形重叠的长度
    /// </summary>
    public static double OverlapLength(LineSegment2d line1, List<Vector2d> poly, double tolerance = 0.0001)
    {
        double len = 0;
        for (int i = 0; i < poly.Count; i++)
        {
            var edge = new LineSegment2d(poly[i], poly[(i + 1) % poly.Count]);
            len += OverlapLength(line1, edge, tolerance);
        }
        return len;
    }
    #endregion

    #region 多边形与多边形关系
    /// <summary>
    /// 大多边形是否包含小多边形, 即: 小多边形的所有点都在大多边形内且边不相交
    /// </summary>
    public static bool IsContains(List<Vector2d> bigPoly, List<Vector2d> smallPoly, double tolerance = 0.0001)
    {
        var bigVisitor = Util.GetPolygonVisitor(bigPoly);
        for (int i = 0; i < smallPoly.Count; i++)
        {
            var curP = smallPoly[i];
            if (!Util.IsPointInPolygon(curP, bigPoly, tolerance)) return false;
            var nextP = smallPoly[(i + 1) % smallPoly.Count];
            var curLine = new LineSegment2d(curP, nextP);

            var flag = bigVisitor.Edges.Any(i =>
            {
                var ps = Util.IntersectLineSegmentAndLineSegment(i.Line, curLine);
                if (ps.Count == 0) return false;
                if (ps.Count == 2) return false;//重合
                                                //相交一点 排除交点在小多边Polygon的端点上
                return !Util.IsNearlySame(ps[0], curP, tolerance) && !Util.IsNearlySame(ps[0], nextP, tolerance);
            });
            if (flag) return false;
        }
        return true;
    }

    /// <summary>
    /// 两个多边形在某个方向上重叠的长度
    /// </summary>
    public static double OverlapLengthOnVector(List<Vector2d> box1, List<Vector2d> box2, Vector2d direction, double tolerance = 0.0001)
    {
        direction = direction.Normalized();
        box1 = box1.Select(i => Util.ProjectOnVector(i, direction)).ToList();
        var b1_min = box1.Min();
        var b1_max = box1.Max();
        box2 = box2.Select(i => Util.ProjectOnVector(i, direction)).ToList();
        var b2_min = box2.Min();
        var b2_max = box2.Max();
        return OverlapLengthOnVector(new LineSegment2d(b1_min, b1_max), new LineSegment2d(b2_min, b2_max), direction, tolerance);
    }

    /// <summary>
    /// 计算两个多边形相接的边长度
    /// </summary>
    public static double CalcJoinLength(List<Vector2d> poly1, List<Vector2d> poly2, double tolerance = 0.0001, double degreeTolerance = 1)
    {
        var len = 0d;
        for (int i = 0; i < poly1.Count; i++)
        {
            var cur1 = poly1[i];
            var next1 = poly1[(i + 1) % poly1.Count];
            var line1 = new LineSegment2d(cur1, next1);
            for (int j = 0; j < poly2.Count; j++)
            {
                var cur2 = poly2[j];
                var next2 = poly2[(j + 1) % poly2.Count];
                var line2 = new LineSegment2d(cur2, next2);
                var tmpLen = OverlapLength(line1, line2, tolerance);
                len += tmpLen;
            }
        }
        return len;
    }
    #endregion

    #region Triangle
    /// <summary>
    /// 将给定的多边形三角化,返回三角化后的点序(和原多边形序列顺逆时针一致), 示例:
    /// <code>
    /// /* 0的位置是原点
    ///  * 5---------4
    ///  * |         |
    ///  * |    2----3
    ///  * |    |
    ///  * 0----1
    ///  */
    ///  var points = new List&lt;Vector2d>()
    ///  {
    ///      new Vector2d(0,0),
    ///      new Vector2d(1,0),
    ///      new Vector2d(1,1),
    ///      new Vector2d(2,1),
    ///      new Vector2d(2,2),
    ///      new Vector2d(0,2),
    ///  };
    ///  Util.Triangle(points).ShouldBe(new List&lt;int> { 0, 1, 2, 2, 3, 4, 2, 4, 5, 2, 5, 0 });
    ///  </code>
    /// </summary>
    /// <remarks>注意: 只能处理简单多边形,参考: <seealso cref="IsNearySimplePolygon(List{Vector2d}, double)"/></remarks>
    public static List<int> Triangle(List<Vector2d> polygon) => TriangleAlg.Triangle(polygon);
    #endregion

    #region RemovePointNearlySame RemovePointNearlyOnLine
    /// <summary>
    /// 移除在同一条直线上的点, 如下: 将会把 p1 和 p2 移除
    /// <code>
    /// 3-----------------2
    /// |                 |
    /// |                 |
    /// 0---p1----p2------1
    /// </code>
    /// </summary>
    /// <remarks>
    /// 注意: 
    /// <list type="bullet">
    /// <item>结尾的且和开头重复的点位也会被移除</item>
    /// <item>先执行<seealso cref="RemoveSamePoint"/>, 即: 先移除近似的点</item>
    /// </list>
    /// </remarks>
    public static List<Vector2d> RemovePointNearlyOnLine(List<Vector2d> points, double tolerance = 0.0001)
    {
        if (points == null || points.Count < 3) return points;
        points = RemovePointNearlySame(points, tolerance);
        for (int i = 0; i < points.Count; i++)
        {
            var pre = points[(i - 1 + points.Count) % points.Count];
            var cur = points[i];
            var next = points[(i + 1) % points.Count];
            if (IsNearlySameLine(pre, cur, next, tolerance))
            {
                points.Remove(cur);
                i--;
                if (points.Count < 3) break;
            }
        }
        return points;
    }

    /// <summary>
    /// 移除挨着的几乎相等的点, tolerance: 表示两个点的距离容差
    /// </summary>
    /// <remarks>注意: 结尾的且和开头重复的点位也会被移除</remarks>
    public static List<Vector2d> RemovePointNearlySame(List<Vector2d> points, double tolerance = 0.0001)
    {
        if (points == null || points.Count < 2) return points;
        if (points.Last() == points.First()) points.RemoveAt(points.Count - 1);
        if (points.Count < 2) return points;
        for (int i = 0; i < points.Count; i++)
        {
            var cur = points[i];
            var next = points[(i + 1) % points.Count];
            if (next.IsNearlySame(cur, tolerance))
            {
                points.RemoveAt((i + 1) % points.Count);
                if (points.Count < 2) break;
            }
        }
        return points;
    }
    #endregion

    #region OffSetPolygon
    /// <summary>
    /// 多边形内缩或外扩, offset>0 外扩, <0 内缩
    /// </summary>
    /// <remarks>
    /// 注意: 没有做极限值处理, 比如:
    /// <list type="bullet">
    /// <item>内缩后简单多边形变成自相交了</item>
    /// <item>外扩导致原本很小的内角两边无限长</item>
    /// </list>
    /// </remarks>
    public static List<Vector2d> OffSetPolygon(List<Vector2d> polygon, double offset)
    {
        var visitor = Util.GetPolygonVisitor(polygon);
        var offsetLines = visitor.Edges.Select(i =>
        {
            var offsetLine = new LineSegment2d(i.PreCorner().Position - i.InnerNormal * offset, i.NextCorner().Position - i.InnerNormal * offset);
            return offsetLine;
        }).ToList();

        var offsetPolygon = new List<Vector2d>(polygon.Count);
        for (int i = 0; i < offsetLines.Count; i++)
        {
            var curLine = offsetLines[i];
            var preLine = offsetLines[(i - 1 + offsetLines.Count) % offsetLines.Count];
            if (IsNearlyParallel(curLine, preLine, 0))
            {
                offsetPolygon.Add(curLine.P0);
            }
            else
            {
                var cross = Util.IntersectLineAndLine(curLine, preLine);
                offsetPolygon.Add(cross);
            }
        }
        return offsetPolygon;
    }
    #endregion

    #region 使用 clipper2 进行图形裁剪运算
    /// <summary>
    /// 两个多边形相交
    /// </summary>
    public static List<List<Vector2d>> IntersectPolygon(List<Vector2d> poly1, List<Vector2d> poly2, int digits = 4)
    {
        //用于误差运算
        var scale = Math.Pow(10, digits);
        var tolerance = 1 / scale;

        var orgin = new List<List<Vector2d>> { poly1, poly2 }; //用于最终吸附点
        var path64_1 = poly1.Select(i => i * scale).Select(i => new Point64((long)Math.Round(i.X), (long)(Math.Round(i.Y))));
        var path64_2 = poly2.Select(i => i * scale).Select(i => new Point64((long)Math.Round(i.X), (long)(Math.Round(i.Y))));

        var subject = new Path64();
        subject.AddRange(path64_1);

        var clip = new Path64();
        clip.AddRange(path64_2);

        // 相交结果容器
        var solution = new Paths64();

        // 创建 Clipper 实例并添加路径
        var clipper = new Clipper64();
        clipper.AddSubject(subject);
        clipper.AddClip(clip);

        // 执行布尔操作：相交
        clipper.Execute(ClipType.Intersection, FillRule.EvenOdd, solution);
        return solution
            .Select(i => i.Select(i => new Vector2d(i.X / (scale * 1.0), i.Y / (scale * 1.0))).ToList())
            .Select(i => AdsorbPoints(i, orgin, tolerance))
            .ToList();
    }

    /// <summary>
    /// 两个多边形是否相交
    /// </summary>
    public static bool IsIntersectPolygon(List<Vector2d> poly1, List<Vector2d> poly2, int digits = 4)
    {
        //用于误差运算
        var scale = Math.Pow(10, digits);

        var path64_1 = poly1.Select(i => i * scale).Select(i => new Point64((long)Math.Round(i.X), (long)(Math.Round(i.Y))));
        var path64_2 = poly2.Select(i => i * scale).Select(i => new Point64((long)Math.Round(i.X), (long)(Math.Round(i.Y))));

        var subject = new Path64();
        subject.AddRange(path64_1);

        var clip = new Path64();
        clip.AddRange(path64_2);

        // 相交结果容器
        var solution = new Paths64();

        // 创建 Clipper 实例并添加路径
        var clipper = new Clipper64();
        clipper.AddSubject(subject);
        clipper.AddClip(clip);

        // 执行布尔操作：相交
        clipper.Execute(ClipType.Intersection, FillRule.EvenOdd, solution);
        return solution.Count > 0;
    }

    /// <summary>
    /// 两个多边形合并
    /// </summary>
    public static List<List<Vector2d>> UnionPolygon(List<Vector2d> poly1, List<Vector2d> poly2, int digits = 4)
    {
        return UnionPolygon(new List<List<Vector2d>> { poly1, poly2 }, digits);
    }

    /// <summary>
    /// 多个多边形合并
    /// </summary>
    public static List<List<Vector2d>> UnionPolygon(List<List<Vector2d>> polys, int digits = 4)
    {
        //用于误差运算
        var scale = Math.Pow(10, digits);
        var tolerance = 1 / scale;

        var path64s = polys.Select(i => i.Select(i => i * scale).Select(i => new Point64((long)Math.Round(i.X), (long)(Math.Round(i.Y)))).ToList()).ToList();

        var subject = new Path64();
        subject.AddRange(path64s.First());

        var clip = new Path64();
        foreach (var poly in path64s.Skip(1))
        {
            clip.AddRange(poly);
        }

        // 相交结果容器
        var solution = new Paths64();

        // 创建 Clipper 实例并添加路径
        var clipper = new Clipper64();
        clipper.AddSubject(subject);
        clipper.AddClip(clip);

        // 执行布尔操作：
        clipper.Execute(ClipType.Union, FillRule.EvenOdd, solution);
        return solution
            .Select(i => i.Select(i => new Vector2d(i.X / (scale * 1.0), i.Y / (scale * 1.0))).ToList())
            .Select(i => AdsorbPoints(i, polys, tolerance))
            .ToList();
    }

    /// <summary>
    /// 两个多边形相减: poly1 - poly2
    /// </summary>
    public static List<List<Vector2d>> SubPolygon(List<Vector2d> poly1, List<Vector2d> poly2, int digits = 4)
    {
        //用于误差运算
        var scale = Math.Pow(10, digits);
        var tolerance = 1 / scale;

        var orgin = new List<List<Vector2d>> { poly1, poly2 }; //用于最终吸附点
        var path64_1 = poly1.Select(i => i * scale).Select(i => new Point64((long)Math.Round(i.X), (long)(Math.Round(i.Y))));
        var path64_2 = poly2.Select(i => i * scale).Select(i => new Point64((long)Math.Round(i.X), (long)(Math.Round(i.Y))));

        var subject = new Path64();
        subject.AddRange(path64_1);

        var clip = new Path64();
        clip.AddRange(path64_2);

        // 相交结果容器
        var solution = new Paths64();

        // 创建 Clipper 实例并添加路径
        var clipper = new Clipper64();
        clipper.AddSubject(subject);
        clipper.AddClip(clip);

        // 执行布尔操作：
        clipper.Execute(ClipType.Difference, FillRule.EvenOdd, solution);
        return solution
            .Select(i => i.Select(i => new Vector2d(i.X / (scale * 1.0), i.Y / (scale * 1.0))).ToList())
            .Select(i => AdsorbPoints(i, orgin, tolerance))
            .ToList();
    }
    #endregion

    #region 点位误差修正 FixPoints AdsorbPoints
    /// <summary>
    /// 将相近的点位数据转成完全相同的坐标数据
    /// </summary>
    public static List<Vector2d> FixPoints(List<Vector2d> points, double tolerance = 0.0001)
    {
        for (int i = 0; i < points.Count - 1; i++)
        {
            var ps = points[i];
            for (int j = i + 1; j < points.Count; j++)
            {
                var ps2 = points[j];
                if (Util.IsNearlySame(ps, ps2, tolerance))
                {
                    points[j] = ps;
                }
            }
        }
        return points;
    }

    /// <summary>
    /// 将相近的点位数据转成完全相同的坐标数据
    /// </summary>
    public static List<Vector2d> FixPointsByExample(List<Vector2d> points, List<Vector2d> example, double tolerance = 0.0001)
    {
        example = example.ToList();
        var count = example.Count;
        example.AddRange(points);
        example = FixPoints(example, tolerance);
        for (int i = 0; i < points.Count; i++)
        {
            points[i] = example[count + i];
        }
        return points;
    }

    /// <summary>
    /// 将 srcPoly 上的点 吸附到 targetPoly 上, 返回 srcPoly 自身
    /// </summary>
    /// <remarks>注意: 不会在 srcPoly 上引入新的点位</remarks>
    public static List<Vector2d> AdsorbPoints(List<Vector2d> srcPoly, List<List<Vector2d>> targetPolys, double tolerance = 0.0001)
    {
        var poly = srcPoly.Select((point, idx) => (point, idx)).ToList();
        var ps = targetPolys.SelectMany(i => i).ToList();
        var lines = targetPolys.SelectMany(poly => poly.Select((i, idx) => new LineSegment2d(i, poly[(idx + 1) % poly.Count]))).ToList();

        for (int j = 0; j < poly.Count; j++)
        {
            var p = poly[j];
            //优先吸附到点
            var list = ps.Select((i, idx) => (idx, dis: i.DistanceTo(p.point))).Where(i => i.dis <= tolerance).OrderBy(i => i.dis).ToList();
            if (list.Count > 0)
            {
                var tmpIdx = list.First().idx;
                srcPoly[p.idx] = ps[tmpIdx];
                continue;
            }

            //再吸附到边上
            var list2 = lines.Select(line => Util.ProjectInSegment(p.point, line)).Select(proj => (proj, dis: p.point.DistanceTo(proj)))
                .Where(i => i.dis <= tolerance).OrderBy(i => i.dis).ToList();
            if (list2.Count > 0)
            {
                srcPoly[p.idx] = list2.First().proj;
                continue;
            }
        }
        return srcPoly;
    }

    /// <summary>
    /// 将 srcPoly 上的点 吸附到 targetPoly 上, 返回 srcPoly 自身
    /// </summary>
    /// <remarks>注意: 不会在 srcPoly 上引入新的点位</remarks>
    public static List<Vector2d> AdsorbPoints(List<Vector2d> srcPoly, List<Vector2d> targetPoly, double tolerance = 0.0001)
    {
        return AdsorbPoints(srcPoly, new List<List<Vector2d>> { targetPoly }, tolerance);
    }

    /// <summary>
    /// 将 srcPoly 和 targetPoly 上的点以及边相互吸附, 以消除缝隙<br/>
    /// 判断缝隙的依据是: 当点到点或点到线的距离在 (minGap,maxGap) 之间
    /// </summary>
    /// <remarks>注意: 为了消除缝隙, 必要时会在 srcPoly 上引入新的点位</remarks>
    public static List<Vector2d> AdsorbPointsV2(List<Vector2d> srcPoly, List<Vector2d> targetPoly, double minGap = 0.0001, double maxGap = 0.001)
    {
        AdsorbPoints(srcPoly, new List<List<Vector2d>> { targetPoly }, maxGap);
        List<(int idx, LineSegment2d line)> allSrcLines = null;
        var refreshSrcLines = () =>
        {
            allSrcLines = srcPoly.Select((i, idx) => (idx, new LineSegment2d(srcPoly[idx], srcPoly[(idx + 1) % srcPoly.Count]))).ToList();
        };
        refreshSrcLines();
        for (int i = 0; i < targetPoly.Count; i++)
        {
            var target = targetPoly[i];

            var list = allSrcLines.Select(i => (i.idx, proj: Util.ProjectInSegment(target, i.line))).Select(i => (i.idx, dis: i.proj.DistanceTo(target))).OrderBy(i => i.dis).ToList();
            if (list.First().dis < minGap) continue;
            if (list.First().dis < maxGap && list.First().dis > minGap)
            {
                //认为有缝隙 增加新的点位
                var idx = list.First().idx;
                if (idx == srcPoly.Count - 1)
                {
                    srcPoly.Add(target);
                }
                else
                {
                    srcPoly.Insert(idx + 1, target);
                }
                refreshSrcLines();
            }
        }
        srcPoly = Util.RemovePointNearlyOnLine(srcPoly, minGap / 10);
        return srcPoly;
    }

    /// <summary>
    /// 将 srcPoly 和 targetPoly 上的点以及边相互吸附, 以消除缝隙<br/>
    /// 判断缝隙的依据是: 当点到点或点到线的距离在 (minGap,maxGap) 之间
    /// </summary>
    /// <remarks>注意: 为了消除缝隙, 必要时会在 srcPoly 上引入新的点位</remarks>
    public static List<Vector2d> AdsorbPointsV2(List<Vector2d> srcPoly, List<List<Vector2d>> targetPolys, double minGap = 0.0001, double maxGap = 0.001)
    {
        AdsorbPoints(srcPoly, targetPolys, minGap);
        List<(int idx, LineSegment2d line)> allSrcLines = null;
        var refreshSrcLines = () =>
        {
            allSrcLines = srcPoly.Select((i, idx) => (idx, new LineSegment2d(srcPoly[idx], srcPoly[(idx + 1) % srcPoly.Count]))).ToList();
        };
        refreshSrcLines();
        for (int k = 0; k < targetPolys.Count; k++)
        {
            var targetPoly = targetPolys[k];
            for (int i = 0; i < targetPoly.Count; i++)
            {
                var target = targetPoly[i];

                var list = allSrcLines.Select(i => (i.idx, proj: Util.ProjectInSegment(target, i.line))).Select(i => (i.idx, dis: i.proj.DistanceTo(target))).OrderBy(i => i.dis).ToList();
                if (list.First().dis < minGap) continue;
                if (list.First().dis < maxGap && list.First().dis > minGap)
                {
                    //认为有缝隙 增加新的点位
                    var idx = list.First().idx;
                    if (idx == srcPoly.Count - 1)
                    {
                        srcPoly.Add(target);
                    }
                    else
                    {
                        srcPoly.Insert(idx + 1, target);
                    }
                    refreshSrcLines();
                }
            }
        }
        srcPoly = Util.RemovePointNearlyOnLine(srcPoly, minGap / 10);
        return srcPoly;
    }

    /// <summary>
    /// 将相近的点位数据转成完全相同的坐标数据
    /// </summary>
    public static List<List<Vector2d>> FixPoints(List<List<Vector2d>> points, double tolerance = 0.0001)
    {
        var counts = points.Select(i => i.Count).ToList();
        var newPoints = points.SelectMany(i => i).ToList();
        newPoints = Util.FixPoints(newPoints, tolerance);
        var offSet = 0;
        for (int i = 0; i < counts.Count; i++)
        {
            var count = counts[i];
            for (int j = 0; j < count; j++)
            {
                points[i][j] = newPoints[offSet++];
            }
        }
        return points;
    }
    #endregion

    #region GetPolygonVisitor
    /// <summary>
    /// 获取polygon访问器
    /// </summary>
    /// <param name="points"></param>
    /// <returns></returns>
    public static PolygonVisitor GetPolygonVisitor(List<Vector2d> points) => new PolygonVisitor(points);

    /// <summary>
    /// 计算polygon的内角,如下:
    /// <code>
    ///      2----3
    ///      |    |
    /// 0----1    4
    /// |         |
    /// 6---------5
    /// </code>
    /// 得到(注意: 返回的是弧度制, 这里用角度值示例):<br/>
    /// 90, 270, 90, 90, 180, 90, 90
    /// </summary>
    public static List<double> GetPolygonRadians(List<Vector2d> points)
    {
        if (!IsNearySimplePolygon(points)) throw new Exception($"必须是简单 polygon 才允许调用 GetPolygonRadians !");
        return getPolygonRadians(points);
    }

    internal static List<double> getPolygonRadians(List<Vector2d> points)
    {
        var IsCCW = IsCounterClockWise(points);
        var len = points.Count;
        if (points.Last() == points.First())
        {
            len--;
        }
        var radians = new List<double>();
        for (var i = 0; i < len; i++)
        {
            var cur = points[i];
            var pre = points[(i - 1 + len) % len];
            var next = points[(i + 1) % len];

            var angle = AngleRadianIgnoreClock(next - cur, pre - cur);
            var cross = Cross(next - cur, pre - cur);
            if (cross == 0)
            {
                //pre->cur->next 三点共线
                radians.Add(Math.PI);
                continue;
            }

            //求 pre->cur->next 的顺逆时针
            var IsLocalCCW = Util.IsCounterClockWise(new List<Vector2d> { pre, cur, next });
            if (IsLocalCCW ^ IsCCW)
            {
                //局部与整体相反,是钝角
                angle = Math.PI * 2 - angle;
            }
            radians.Add(angle);
        }
        return radians;
    }

    /// <summary>
    /// 计算polygon的边的内向法向量,如下:
    /// <code>
    ///        ①
    ///   0----↓----1
    ///   |          |
    /// ④→        ←②
    ///   |          |
    ///   3----↑----2
    ///        ③
    /// </code>
    /// </summary>
    public static List<Vector2d> GetPolygonEdgeNormals(List<Vector2d> points)
    {
        if (!IsNearySimplePolygon(points)) throw new Exception($"必须是简单 polygon 才允许调用 GetPolygonRadians !");
        return getPolygonEdgeNormals(points);
    }

    internal static List<Vector2d> getPolygonEdgeNormals(List<Vector2d> points)
    {
        //先算出内角
        var radians = getPolygonRadians(points);
        return getPolygonEdgeNormals(points, radians);
    }

    internal static List<Vector2d> getPolygonEdgeNormals(List<Vector2d> points, List<double> radians)
    {
        var len = points.Count;
        if (points.Last() == points.First()) len--;
        var normals = new List<Vector2d>();
        var remainIndex = new List<int>();
        for (int i = 0; i < len; i++)
        {
            var curIndex = i;
            var nextIndex = (curIndex + 1) % len;
            var next2Index = (curIndex + 2) % len;
            var curP = points[curIndex];
            var nextP = points[nextIndex];
            var next2P = points[next2Index];

            var nextDir = (next2P - nextP).Normalized();
            var curDir = (nextP - curP).Normalized();
            var nextAngle = radians[nextIndex].ToDegree();
            var normal1 = new Vector2d(-curDir.Y, curDir.X);//逆时针转90度
            var normal2 = new Vector2d(curDir.Y, -curDir.X);//顺时针转90度
            var angleDegree = normal1.AngleRadian(nextDir).NormalRadianLikeVectorIgnoreClock().ToDegree();

            /* 逆时针
             * cur: A, next: B, next2: C
             *     C
             *    / \
             *   /   \
             *  /     \
             * A-------B
             */
            if (nextAngle < 180)
            {
                //当∠ABC < 180° 时，AB边的法向向量方向与BC向量的夹角小于90°
                if (angleDegree < 90) normals.Add(normal1);
                else normals.Add(normal2);
            }
            else if (nextAngle > 180)
            {
                //当∠ABC > 180° 时，AB边的法向向量方向与BC向量的夹角大于90°
                if (angleDegree > 90) normals.Add(normal1);
                else normals.Add(normal2);
            }
            else
            {
                //等于180 三点共线
                normals.Add(Vector2d.Zero);
                remainIndex.Add(curIndex);
            }
        }
        if (remainIndex.Count > 0)
        {
            for (int i = 0; i < remainIndex.Count; i++)
            {
                var curIndex = remainIndex[i];
                var nextIndex = (curIndex + 1) % len;
                var next2Index = (curIndex + 2) % len;


                var end = nextIndex;
                var t = next2Index;
                while (t != end)
                {
                    if (radians[t] != Math.PI)
                    {
                        normals[curIndex] = normals[(t - 1 + len) % len];
                        break;
                    }
                    else
                    {
                        t++;
                        t = t % len;
                    }
                }
            }
        }

        return normals;
    }
    #endregion

    #region ProjectTo2d UnProjectTo3d GetBoxOriginAndUV GetBoxAndUVs
    /// <summary>
    /// 将三维平面的点投影到二维平面内, 指定二维平面的原点和xy轴向量
    /// </summary>
    /// <remarks>
    /// 注意: unitX 和 unitY 的长度对结果有影响
    /// </remarks>
    public static List<Vector2d>? ProjectTo2d(List<Vector3d> points, Vector3d origin, Vector3d unitX, Vector3d unitY)
    {
        if (points == null) return null;
        var xLen = unitX.Length();
        var yLen = unitY.Length();
        return points.Select(i =>
        {
            var v = i - origin;
            if (v.Length() == 0) return new Vector2d(0, 0);
            var shadowX = Util.Dot(v, unitX) / xLen;
            shadowX /= xLen;
            var shadowY = Util.Dot(v, unitY) / yLen;
            shadowY /= yLen;
            return new Vector2d(shadowX, shadowY);
        }).ToList();
    }

    /// <summary>
    /// 将二维平面内的点反投影回三维内, 参考: <see cref="ProjectTo2d(List{Vector3d}, Vector3d, Vector3d, Vector3d)"/>
    /// </summary>
    /// <remarks>
    /// 注意: <br/>
    /// 不可能将三维的东西(如: 桌子)投影到二维, 然后再投影过去。<br/>
    /// 不过, 可以将三维中的面(如: 纸张)投影到二维, 再投影回去, 只要选定合适的投影参数。
    /// <br/><br/>
    /// 另外, unitX 和 unitY 的长度对结果有影响
    /// </remarks>
    public static List<Vector3d>? UnProjectTo3d(List<Vector2d> points, Vector3d origin, Vector3d unitX, Vector3d unitY)
    {
        if (points == null) return null;
        return points.Select(i =>
        {
            return i.X * unitX + i.Y * unitY + origin;
        }).ToList();
    }

    /// <summary>
    /// 计算给定三维点所在平面内的包围盒,返回: 盒子左下角,u/v方向归一化向量以及u/v方向的长度
    /// </summary>
    /// <remarks>
    /// 注意: 传入的点位要是一个平面内的才有意义
    /// </remarks>
    public static (Vector3d origin, Vector3d vectorU, Vector3d vectorV, double boxLenU, double boxLenV) GetBoxOriginAndUV(List<Vector3d> points, Vector3d? vectorU = null, Vector3d? vectorV = null)
    {
        var normal = Util.GetPolygonNormal(points);
        Vector3d u, v;

        Vector3d origin = Vector3d.Zero;
        if (vectorU == null || vectorV == null)
        {
            //最长边为u方向
            var maxLen = 0d;
            var maxIdx = -1;
            for (int i = 0; i < points.Count; i++)
            {
                var cur = points[i];
                var next = points[(i + 1) % points.Count];
                var len = (next - cur).Length();
                if (len > maxLen)
                {
                    maxLen = len;
                    maxIdx = i;
                }
            }
            origin = points[maxIdx];
            u = (points[(maxIdx + 1) % points.Count] - points[maxIdx]).Normalized();
            v = Util.Cross(normal, u).Normalized();
        }
        else
        {
            u = vectorU.Value.Normalized();
            v = vectorV.Value.Normalized();
        }

        //分别计算投影
        var uvs = points.Select(i => new Vector2d(Util.Dot(i - origin, u), Util.Dot(i - origin, v))).ToList();

        //适应修改 origin u,使 所有点的u都在 [0,1] 之间
        var xs = uvs.Select(i => i.X);
        var minX = xs.Min();
        var maxX = xs.Max();
        var lenX = maxX - minX;
        //需要平移
        origin = origin + u * minX;

        //适应修改 origin v,使 所有点的v都在 [0,1] 之间
        var ys = uvs.Select(i => i.Y);
        var minY = ys.Min();
        var maxY = ys.Max();
        var lenY = maxY - minY;
        //需要平移
        origin = origin + v * minY;

        return (origin, u, v, lenX, lenY);
    }

    /// <summary>
    /// 求一平面内任意形状多边形的包裹 box(左下->右下->右上->左上), 及已有点的 uv 值
    /// </summary>
    /// <remarks>
    /// 注意: 传入的点位要是一个平面内的才有意义
    /// </remarks>
    public static (List<Vector2d> uvs, List<Vector3d> box, Vector3d origin, Vector3d vectorU, Vector3d vectorV) GetBoxAndUVs(List<Vector3d> points, Vector3d? vectorU = null, Vector3d? vectorV = null)
    {
        var (origin, u, v, lenX, lenY) = GetBoxOriginAndUV(points, vectorU, vectorV);

        //重新计算uvs
        var uvs = points.Select(i => new Vector2d(Util.Dot(i - origin, u) / lenX, Util.Dot(i - origin, v) / lenY)).ToList();
        u *= lenX;
        v *= lenY;

        //得到包围盒
        var box = UnProjectTo3d(new List<Vector2d>
        {
            new Vector2d(0,0),
            new Vector2d(1,0),
            new Vector2d(1,1),
            new Vector2d(0,1),
        }, origin, u, v);
        return (uvs, box, origin, u, v);
    }
    #endregion
}